Formula for some average

I am finding a formula for the average $A_n$ of the numbers $(a_1-a_2)^2 + \cdots + (a_{n-1} - a_n )^2$ over all cases that $\{a_1, \cdots, a_n \} = \{ 1,2, \cdots, n\}$.

For example, $A_2=1, A_3=4, A_4=10, A_5=20, A_6=35, \cdots$. From this, I guess: $$A_n = \frac{1}{6} (n-1) n (n+1).$$

Can anyone prove it or give correct formula?

Solution 1:

From your results, one can coclude that you calculate average of all permutation of set. Then due to symmetry $A_n=(n-1) B_n$ , where $B_n$ is average of $(a_1-a_2)^2$ for all possible pairs $(a_1,a_2)$. $B_n$ could be found directly:

$$B_n=\frac{2}{n(n-1)}\sum_{a_1=1}^{n-1} \sum_{a_2=a_1+1}^{n} (a_1-a_2)^2=\frac{1}{6}n(n+1)$$

Then $$A_n=\frac{1}{6}n(n-1)(n+1)$$