Valore Medio di Somme di Permutazioni

Problema

Sia data una permutazione \((a_{1},a_{2}, \cdots ,a_{n})\) dell’insieme \({1,2, \cdots,n }\). Calcolare il valore medio, indicato con \(M_{n}\), della seguente somma:

\[ (a_{1}- a_{2})^2 + (a_{2}-a_{3})^2 + \cdots + (a_{n-1} – a_{n})^2 \]

presa su tutte le permutazioni.

Nel caso \(n=2\) l’insieme delle permutazioni è \({12,21}\) e quindi \(M_{2}=1\). Nel caso \(n=3\) l’insieme delle permutazioni è \({123,132,213,231,312,321}\). Con pochi calcoli si trova facilmente \(M_{3}=4\).

Soluzione

Per n=4 si hanno \(24=4!\) permutazioni; mettendo insieme tutte le 24 somme, ognuno di 3 addendi, possiamo considerare un’unica somma di 72 addendi divisa per \(24\). Le differenze da fare al quadrato possono assumere i valori 1,2,3. Distinguiamo i tre casi:

A) Differenza = 1
Può essere ottenuta con le coppie (12),(23),(34),(21),(32),(43). Il numero delle coppie possibili è \( 6=3 \cdot 2\). Ognuna di queste coppie può trovarsi in \(3=4-1\) posizioni diverse in ogni permutazione (ad esempio per la coppia (12) abbiamo 12xx,x12x,xx12). Inoltre per ogni singola situazione abbiamo \(2!=(4-2)!\) diverse disposizioni degli altri numeri. Quindi in definitiva il numero dei casi possibili è:

\[ N_{1}= 6 \cdot 3 \cdot 2!=36 \]

B) Differenza = 2
Può essere ottenuta con le coppie (13),(24),(31),(42). Il numero delle coppie possibili è \(4\). Ognuna di queste coppie può trovarsi in 3 posizioni diverse in ogni permutazione. Inoltre per ogni singola situazione abbiamo 2! diverse disposizioni degli altre numeri. Quindi in definitiva il numero dei casi possibili è:

\[ N_{2}=4 \cdot 3 \cdot 2!=24 \]

C) Differenza = 3
Può essere ottenuta con le coppie (14),(41). Il numero delle coppie possibili è \(2\). Ognuna di queste coppie può trovarsi in 3 posizioni diverse in ogni permutazione. Inoltre per ogni singola situazione abbiamo 2! diverse disposizioni degli altre numeri. Quindi in definitiva il numero dei casi possibili è:

\[ N_{3}=2\cdot 3 \cdot 2!=12 \]

Calcoliamo le somme parziali:
\(S_{1}= N_{1} \cdot 1^2 = 36\)
\(S_{2}= N_{2} \cdot 2^2 = 96\)
\(S_{3}= N_{3} \cdot 3^2 = 108\)

Il valore della media è quindi:

\[ M_{4}=\frac {S_{1}+ S_{2}+ S_{3}}{24}=10 \]

Applicando lo stesso ragionamento al caso generale si trova la seguente soluzione:

\[ M_{n}=\frac{2(n-1)(n-2)!\displaystyle \sum_{k=1}^{k=n-1}k^2 (n-k)}{n!} \]

Per semplificare questa espressione utilizziamo la formula per la somma dei quadrati dei primi \(n\) numeri naturali:

\[ \displaystyle \sum_{k=1}^{k=n}k^2 = \frac{n(n+1)(2n+1)}{6} \]

e la formula per la somma dei cubi dei primi \(n\) numeri naturali:

\[ \displaystyle \sum_{k=1}^{k=n}k^3 = \frac{n^2(n+1)^2}{4} \]

Utilizzando queste due formule otteniamo infine:

\[ M_{n}= \frac{(n-1)n(n+1)}{6}= \binom {n+1}{3} \]