```python
import math
import numpy as np
import functools
import sympy as sym
```

## Valid permutations example: D=2, L=2, R=2
- $\textbf{[D,L,R,R,D,L]}$
- $\textbf{[L,L,D,R,R,D]}$
- $\textbf{[L,R,D,L,R,D]}$

## Rules:
- Permutations must not end in R
- Permutations must not include an R followed by an L

## Invalid permutations examples: D=2, L=2, R=2
- $\textbf{[D,D,L,L,R,R]}$

- $\textbf{[R,L,L,D,R,D]}$

## Total number of permutations ($T$):
$$T = \frac{(D+R+L)!}{D! \times R! \times L!}$$


```python
def get_all_permutations(D, R, L):
    return np.math.factorial(D + R + L) // (np.math.factorial(D) * np.math.factorial(R) * np.math.factorial(L))
```


```python

```

## Number of permutations that end in R ($E_R$):
$$
E_R = 
\begin{cases}
    \frac{(D+R+L-1)!}{D! \times (R-1)! \times L!} & \text{if } R>0\\
    0 & \text{otherwise}
\end{cases}    
$$


```python
def get_permutations_ending_in_R(D, R, L):
    if R > 0:
        return np.math.factorial(D + R + L - 1) // (np.math.factorial(D) * np.math.factorial(R-1) * np.math.factorial(L))
    else:
        return 0
```

### Examples:
- $[R,D,L,D,L,|R]$
- $[D,L,L,R,D,|R]$
- $[D,R,D,L,L,|R]$
- $[L,D,R,D,L,|R]$


```python

```

## Number of permutations that end in D and there exist at least one RL ($E_D$):

$$
E_D = 
\begin{cases}
    \sum_{i=1}^{\min(R,L)} (-1)^{i+1} \frac{(D+R+L-i-1)!}{(D-1)! \times (R-i)! \times (L-i)! \times (i)!} & \text{if } \min(R,L) > 0\\
    0 & \text{otherwise}
\end{cases}    
$$


```python
def get_permutations_ending_in_D_where_any_RL_exists(D, R, L, method=np.math):
    max_RL = min(R,L)
    if max_RL > 0:
        sign = -1
        perms = 0
        for num_RL in np.linspace(1, max_RL, max_RL):
            sign *= -1
            current_perm = method.factorial(R + D + L - num_RL - 1) // (method.factorial(D-1) * method.factorial(R-num_RL) * method.factorial(L-num_RL) * method.factorial(num_RL))
            perms += sign * current_perm

        return perms
    else:
        return 0
```

### Examples:
- $[R,D,L,(RL),|D]$
- $[(RL),L,R,D,|D]$
- $[D,R,(RL),L,|D]$
### Duplicate cases:
- $[D,R,L,(RL),|D]$ 
- $[D,(RL),R,L,|D]$
- $[D,(RL),(RL),|D]$


```python

```

## Number of permutations that end in L and there exist at least one RL ($E_L$):

$$
E_L = 
\begin{cases}
    \sum_{i=1}^{\min(R,L)} (-1)^{i+1} \frac{(D+R+L-i-1)!}{(D)! \times (R-i)! \times (L-i-1)! \times (i)!} & \text{if } \min(R,L-1) > 0\\
    0 & \text{otherwise}
\end{cases}    
$$


```python
def get_permutations_ending_in_L_where_any_RL_exists(D, R, L):
    max_RL = min(R,L-1)
    if max_RL > 0:
        sign = -1
        perms = 0
        for num_RL in np.linspace(1, max_RL, max_RL):
            sign *= -1
            perms += sign * np.math.factorial(R + D + L - num_RL - 1) // (np.math.factorial(D) * np.math.factorial(R-num_RL) * np.math.factorial(L-1-num_RL) * np.math.factorial(num_RL))
        return perms
    else:
        return 0
```

### Examples:
- $[R,D,D,(RL),|L]$
- $[(RL),D,R,D,|L]$
- $[D,(RL),D,R,|L]$
### Extra cases:
- $[D,R,D,L,R,|L]$ 
- $[D,L,R,D,R,|L]$
- $[D,D,L,R,R,|L]$


```python

```

## Number of permutations that end in RL and RL exists only at the end ($E_{RL}$):

$$
E_{RL} = 
\begin{cases}
    \sum_{i=1}^{\min(R,L)} (-1)^{i+1} \frac{(D+R+L-i-1)!}{(D)! \times (R-i)! \times (L-i)! \times (i-1)!} & \text{if } \min(R,L) > 0\\
    0 & \text{otherwise}
\end{cases}    
$$


```python
def get_permutations_ending_in_RL_where_RL_exists_only_at_the_end(D, R, L):
    max_RL = min(R,L)
    if max_RL > 0:
        sign = -1
        perms = 0
        for num_RL in np.linspace(1, max_RL, max_RL):
            sign *= -1
            perms += sign * np.math.factorial(R + D + L - num_RL - 1) // (np.math.factorial(D) * np.math.factorial(R-num_RL) * np.math.factorial(L-num_RL) * np.math.factorial(num_RL-1))
        return perms
    else:
        return 0
```

### Examples:
- $[R,D,L,D,|R,L]$
- $[D,L,D,R,|R,L]$
- $[D,R,D,L,|R,L]$
### Cases that should not be considered:
- $[D,R,L,D,|R,L] \rightarrow [D,(RL),D,R,|L]$
- $[R,L,D,D,|R,L] \rightarrow [(RL),D,D,R,|L]$


```python

```

## Number of permutations where there is no R at the end and there is no R followed by an L:

$$
C = T - E_R - E_D - E_L - E_{RL}
$$


```python
def get_coeff(D, R, L):

    total = D + R + L
    all_permutations = get_all_permutations(D, R, L)
    permutations_ending_in_R = get_permutations_ending_in_R(D, R, L)
    permutations_ending_in_D_where_any_RL_exists = get_permutations_ending_in_D_where_any_RL_exists(D, R, L)
    permutations_ending_in_L_where_any_RL_exists = get_permutations_ending_in_L_where_any_RL_exists(D, R, L)
    permutations_ending_in_RL_where_RL_exists_only_at_the_end = get_permutations_ending_in_RL_where_RL_exists_only_at_the_end(D, R, L)

    coeff = all_permutations 
    coeff -= permutations_ending_in_R 
    coeff -= permutations_ending_in_D_where_any_RL_exists 
    coeff -= permutations_ending_in_L_where_any_RL_exists
    coeff -= permutations_ending_in_RL_where_RL_exists_only_at_the_end

    return coeff#, [all_permutations, permutations_ending_in_R, permutations_ending_in_D_where_any_RL_exists, permutations_ending_in_L_where_any_RL_exists, permutations_ending_in_RL_where_RL_exists_only_at_the_end]
```


```python
get_coeff(10,0,1)
```




    11




```python

```

# All known coefficients


```python
demo = [[1,1,1],
        [2,1,1],
        [1,2,1],
        [1,1,2],
        [3,1,1],
        [2,2,1],
        [2,1,2],
        [1,3,1],
        [1,2,2],
        [1,1,3],
        [4,1,1],
        [3,2,1],
        [3,1,2],
        [2,3,1],
        [2,2,2],
        [2,1,3],
        [1,4,1],
        [1,3,2],
        [1,2,3],
        [1,1,4],
        [5,1,1],
        [4,2,1],
        [4,1,2],
        [3,3,1],
        [3,2,2],
        [3,1,3],
        [2,4,1],
        [2,3,2],
        [2,2,3],
        [2,1,4],
        [1,5,1],
        [1,4,2],
        [1,3,3],
        [1,2,4],
        [1,1,5],
        [6,1,1],
        [5,2,1],
        [5,1,2],
        [4,3,1],
        [4,2,2],
        [4,1,3],
        [3,4,1],
        [3,3,2],
        [3,2,3],
        [3,1,4],
        [2,5,1],
        [2,4,2],
        [2,3,3],
        [2,2,4],
        [2,1,5],
        [1,6,1],
        [1,5,2],
        [1,4,3],
        [1,3,4],
        [1,2,5],
        [1,1,6]]
```


```python
for drl in demo:
    print(get_coeff(drl[0], drl[1], drl[2]))
```

    2
    6
    2
    3
    12
    9
    12
    2
    3
    4
    20
    24
    30
    12
    18
    20
    2
    3
    4
    5
    30
    50
    60
    40
    60
    60
    15
    24
    30
    30
    2
    3
    4
    5
    6
    42
    90
    105
    100
    150
    140
    60
    100
    120
    105
    18
    30
    40
    45
    42
    2
    3
    4
    5
    6
    7



```python

```

# Large inputs


```python
get_coeff(1, 100, 100)
```




    (101,
     [18200251445876759514246239592574316938775422524758080705105320,
      9054851465610328116540417707748416387450458967541333684132000,
      90548514656103281165404177077484163874504589675413336841319,
      9054851465610328116540417707748416387450458967541333684121900,
      10000])




```python

```

## Check values that the algorithm holds


```python
@functools.lru_cache(maxsize=None)
def a(n):
    if n >= 2: 
        return 3*a(n-1) - a(n-2)
    else:
        return 1
```


```python
# 1, 2, 5, 13, 34, 89, 233, 64

def verify_permutation_algorithm(cap):
    tot = 0
    for p1 in range(1, cap + 1):
        for p2 in range(0, (cap - p1 + 1)):
            p3 = cap - p1 - p2
            tot += get_coeff(p1,p2,p3)[0]
            # print(p1, p2, p3, get_coeff(p1,p2,p3))
    tot += get_coeff(0,0,1)[0]

    return(a(cap + 1) == tot)
```


```python
for i in range(200,201):
    print(i, verify_permutation_algorithm(i))
```

    200 True


506b95013434089d45acd7bcc7177c5b72c78541
ipynb
Jupyter Notebook
nbs/src/Markov/closed_form_formula_of_pi/Permutations_algorithm.ipynb
11michalis11/AmbulanceDecisionGame
45164ba51da0417297f715e41716cb91facc120f
MIT
nbs/src/Markov/closed_form_formula_of_pi/Permutations_algorithm.ipynb
11michalis11/AmbulanceDecisionGame
45164ba51da0417297f715e41716cb91facc120f
MIT
2020-04-20T09:08:31.000Z
2021-09-23T11:09:25.000Z
nbs/src/Markov/closed_form_formula_of_pi/Permutations_algorithm.ipynb
11michalis11/AmbulanceDecisionGame
45164ba51da0417297f715e41716cb91facc120f
MIT
Qwen/Qwen-72B
1. YES
2. YES