Contents

## 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}$