Mean Value of Permutation Sums

Problem

Let \((a_{1},a_{2}, \cdots ,a_{n})\) be a permutation of the set \(\{1,2, \cdots,n \}\). Compute the average value, indicated with \(M_{n}\) , of the following sum:

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

taken on all permutations.

If \(n=2\) the set of permutations is \(\{12,21\}\) and therefore \(M_{2}=1\).
If \(n=3\) the set of permutations is \( \{123,132,213,231,312,321\}\). With a few calculations it is easily found \( M_{3}=4\).

Solution

For \(n = 4\) we have \(24=4!\) permutations; putting together all the \(24\) sums, each consisting of \(3\) addends, we can consider a single sum of \(72\) addends divided by \(24\). The differences can take the values ​​\(1,2,3\). We distinguish the three cases:

A) Difference = 1
It can be obtained with the couples \((12), (23), (34), (21), (32), (43)\). The number of possible couples is \(6=3 \cdot 2\). Each of these couples can be in \(3=4-1\) different positions in each permutation (for example for the couple \((12)\) we have \((12xx, x12x, xx12)\)). Moreover for every single situation we have \(2!=(4-2)!\) different dispositions of the other numbers. So ultimately the number of possible cases is:

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

B) Difference = 2
It can be obtained with the couples \( (13), (24), (31), (42)\). The number of possible couples is 4. Each of these couples can be in 3 different positions in each permutation. Also for every single situation we have 2! different dispositions of the other numbers. So ultimately the number of possible cases is:

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

C) Difference = 3
It can be obtained with the couples \((14), (41)\). The number of possible pairs is \(2\). Each of these pairs can be in \(3\) different positions in each permutation. Also for every single situation we have \(2!\) different dispositions of the other numbers. So ultimately the number of possible cases is:

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

Now we compute the partial sums:

\[ \begin{array}{l} S_{1}= N_{1} \cdot 1^2 = 36 \\ S_{2}= N_{2} \cdot 2^2 = 96 \\ S_{3}= N_{3} \cdot 3^2 = 108 \\ \end{array} \]

The average value is therefore:

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

Applying the same reasoning to the general case we find the following solution:

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

To simplify this expression we use the formula for the sum of the squares of the first \(n\) natural numbers:

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

and the formula for the sum of the cubes of the first \(n\) natural numbers:

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

Finally, using these two formulas we obtain:

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