Somme des carrés des différences dans les permutations

International

Source : Collection Aassila — Olympiades de Mathématiques

Énoncé du problème

Pour toute permutation $σ = (a_{1}, a_{2}, \dots, a_{n})$ de ${1, 2, \dots, n}$ on pose :

$S_{σ} = (a_{1} - a_{2})^{2} + (a_{2} - a_{3})^{2} + \dots + (a_{n - 1} - a_{n})^{2}$

Montrer que

$\frac{1}{n !} \sum S_{σ} = (3 n + 1)$

où la somme est prise sur les $n!$ permutations de ${1, \dots, n}$ .