var v=new Array(n).fill().map(
x => (Math.random()<0.5)?
[Math.floor(Math.random()*2)*2 -1,0]:
[0,Math.floor(Math.random()*2)*2 -1]
);
oppure, più semplicemente:
var lv=[[1,0],[0,1],[-1,0],[0,-1]]
var v=new Array(n).fill().map(x => lv[Math.floor(Math.random()*4)]);
ricorrendo adesempio nel primo modo
var P=v.reduce((total,x,i)=>
[...total,
[(i>0)? total[i-1][0]+ x[0]:x[0],
(i>0)?total[i-1][1]+x[1]:x[1]]
]
,[]
);
o nel secondo modo
P=v.reduce(
(total,x,i)=>
[...total,
(i>0)?
[total[i-1][0]+ Math.cos(x*Math.PI/2),total[i-1][1]+Math.sin(x*Math.PI/2)]
:[Math.cos(x*Math.PI/2),Math.sin(x*Math.PI/2)]
],[]
);
Ci si potrebbe anche accontentare della sola la posizione finale
var posFin=v.reduce((total,x)=> [total[0]+ x[0],total[1]+x[1]],[0,0]);
Iniziamo col condurre alcune semplici riflessioni per contare il numero dei diversi percorsi di $n$ passi che conducono a una delle possibili posizioni finali.
1 |
||||||||||||
1 |
o |
1 |
per |
n = |
1 |
|||||||
1 |
||||||||||||
1 |
||||||||||||
2 |
2 |
|||||||||||
1 |
4 |
1 |
per |
n = |
2 |
|||||||
2 |
2 |
|||||||||||
1 |
||||||||||||
1 |
||||||||||||
3 |
3 |
|||||||||||
3 |
9 |
3 |
||||||||||
per |
n = |
3 |
1 |
9 |
o |
9 |
1 |
|||||
3 |
9 |
3 |
||||||||||
3 |
3 |
|||||||||||
1 |
... eccetera.
Si noti che le posizioni raggiunte stanno su quadrati concentrici di equazioni $|x|+|y|=k$ dove $k=n \mod 2, n\mod 2 +2, n\mod 2 +4, \cdots, n$
Il numero di percorsi per raggiungere dopo $n$ passi una certa posizione $(x,y)$ forma uno schema numerico che ricorsivamente può descriversi in javascript nel modo seguente:
function nPercorsi(n,x,y) {
if (n==0) return 1
else if(n<Math.abs(x) +Math.abs(y) ) return 0
else if((n+Math.abs(x) +Math.abs(y))%2>0) return 0
else if(n==Math.abs(x) || n==Math.abs(y) ) return 1
else return nPercorsi(n-1,x-1,y)+nPercorsi(n-1,x+1,y)+nPercorsi(n-1,x,y-1)+nPercorsi(n-1,x,y+1)
}
Si tratta di schemi che, ruotati opportunamente, sono generabili anche con una function come quella a fianco che produce ad esempio per n=
| 1 | 3 | 3 | 1 |
| 3 | 9 | 9 | 3 |
| 3 | 9 | 9 | 3 |
| 1 | 3 | 3 | 1 |
var M=[[1,1],[1,1]];
var M1, M2, M3, M4;
for (var i=0;i<n;i++){
M1=[...M.map(r =>[...r,0]),new Array(i+3).fill(0)]
M2=[new Array(i+3).fill(0),...M.map(r =>[...r,0])]
M3=[...M.map(r =>[0,...r]),new Array(i+3).fill(0)]
M4=[new Array(i+3).fill(0),...M.map(r =>[0,...r])]
M=M1.map(
(r,j)=>
r.map(
(e,i)=>
e+M2[j][i]+M3[j][i]+M4[j][i]
)
)
}
Si riconosce una generalizzazione del triangolo di Tartaglia ottenibile a parire dalla matrice $M=[1]$ reiterando la somma \[M=\begin{bmatrix} M & \begin{matrix}0 \\ \vdots\\ 0\end{matrix} \\ \begin{matrix}0\cdots 0\end{matrix} & 0 \end{bmatrix}+ \begin{bmatrix} \begin{matrix}0 \\ \vdots\\ 0\end{matrix} & M \\ 0 &\begin{matrix}0\cdots 0\end{matrix} \end{bmatrix}+ \begin{bmatrix} 0 & \begin{matrix}0\cdots 0\end{matrix} \\ \begin{matrix}0 \\ \vdots\\ 0\end{matrix} & M \end{bmatrix}+ \begin{bmatrix} \begin{matrix}0\cdots 0\end{matrix} &0 \\ M &\begin{matrix}0 \\ \vdots\\ 0\end{matrix} \end{bmatrix}\]
Come già visto in precedenza le probabilità si possono ottenere calcolando una media delle matrici anche anziché una somma.
Si osserva facilmente che i coefficienti al rigo $i$ e colonna $j$ sono $\binom{n}{i}\cdot \binom{n}{j}$.
Dunque il n° di percorsi di $n$ passi che conducono alla posizione $(x,y)$ è \[\begin{cases}\binom{n}{\frac{n+|x|+|y|}{2}}\cdot\binom{n}{\frac{n+|x|-|y|}{2}}&\mbox{quando}\;\;n+x+y\;\; \mbox{è pari e } |x|+|y|\le n\\ 0 &\mbox{altrimenti} \end{cases} \]( si osservi che con un numero dispari $n$ di passi sono raggiungibili solo posizioni con $y\pm x$ dispari, con un numero pari $n$ di passi sono raggiungibili solo posizioni con $y\pm x$ pari).
Ad esempio per n=| 0 | 1 | 0 |
| 1 | 0 | 1 |
| 0 | 1 | 0 |
Lo stesso risultato ottenuto con i binomiali si può ottenere anche come segue, sommando in sostanza i numeri dei percorsi che conducono nelle posizioni vicine per enumerare quelli che portano a una posizione qualunque:
var M1=[[1]];
for(var i=M1.length+2; i<2n+2; i+=2) {
M=[new Array(i).fill(0),...M1.map(r =>[0,...r,0]),new Array(i).fill(0)];
M1=M.map(()=>new Array(i).fill(0));
for(var r=0; r<i; r++)
for(var c=0; c<i; c++)
M1[r][c]=(M[r][c]>0)? 0
: ((r<i-1)? M[r+1][c]: 0) +
((r>0)? M[r-1][c]: 0) +
((c<i-1)? M[r][c+1]: 0) +
((c>0)? M[r][c-1]: 0)
}
Questo schema numerico è detto piramide di Pascal a base quadrata.
Si tratta anche dei coefficienti dello sviluppo di $\displaystyle (x+y+x^{-1}+y^{-1})^n=\sum_{X,Y}c_n(X,Y)x^Xy^Y$ dove $(X,Y)$ è la posizione raggiunta.
Da $\displaystyle (x+y+x^{-1}+y^{-1})^n=\sum_{i_1+i_2+i_3+i_4=n}\binom{n}{i_1\;\; i_2\;\; i_3\;\; i_4}x^{i_1}y^{i_2}x^{-i_3}y^{-i_4}=$
$\displaystyle =\sum_{i_1+i_2+i_3+i_4=n}\binom{n}{i_1\;\; i_2\;\; i_3\;\; i_4}x^{i_1-i_3}y^{i_2-i_4}=$ da $\begin{cases}i_2+i_3+i_4=n-i_1\\i_3= i_1-X\\i_2-i_4=Y \end{cases}$
$\displaystyle =\sum_{X,Y}\sum_{i_1=0}^n\frac{n!}{i_1!\big(\frac{n+X+Y}{2}-i_1\big)!(i_1-X)!\big(\frac{n+X-Y}{2}-i_1\big)!}x^Xy^Y$
si ottiene per $X$ e $Y$ non negativi
$\displaystyle c_n(X,Y)=\binom{n}{\frac{n+X+Y}{2}}\sum_{i=0}^n\binom{\frac{n+X+Y}{2}}{i}\binom{\frac{n-(X+Y)}{2}}{i-X}$ e dalla proprietà dei binomiali $\displaystyle \binom{m+n}{l}=\sum_{i=0}^l\binom{m}{i}\binom{n}{l-i}$ (identità di Vandermonde), da cui anche $\displaystyle \binom{m+n}{n+l}=\sum\binom{m}{i}\binom{n}{i-l}$, deriva appunto \[ c_n(X,Y)=\binom{n}{\frac{n+|X|+|Y|}{2}}\binom{n}{\frac{n+|X|-|Y|}{2}}\]
Si osservi che $|x|+|y|=n-2k \longrightarrow c_n(x,y)=\binom{n}{k}\binom{n}{|x|+k}=\binom{n}{k}\binom{n}{|y|+k}$.
Possiamo visualizzare tali valori attribuendo loro uno dei $256^3-1$ colori $C=256^2R+256G+B$, dove $R,G,B$ sono le intensità, tra 0 e 255, dei colori rosso, verde, blu, da cui si ricava:
B = C % 256
G = ((C-B)/256) % 256
R = ((C-B)/256**2) - G/256