O problema cu permutari

[Bogdan Posa]

Fie \( f(\sigma)= \sum_{k=1}^{n} { |\sigma(k)-k| \). Sa se calculeze \( S= \sum_{\sigma \in S_{n}}f(\sigma) \)

[Beniamin Bogosel]

\( f(\sigma)=\sum\limits_{k=1}^n|\sigma(k)-k| \).
Deci \( \sum_{\sigma}f(\sigma)=\sum_\sigma\sum\limits_{k=1}^n|k-\sigma(k)|=\sum\limits_{k=1}^n\sum_\sigma|k-\sigma(k)|. \)
Acum ramine de calculat pentru fiecare \( k \) suma
\( S_k=\sum_\sigma|k-\sigma(k)| \).

Avem ca \( \sigma(k)=i,\ 1\leq i\leq n \) pentru \( (n-1)! \) permutari \( \sigma \).
Deci \( S_k=\sum_{\sigma}|k-\sigma(k)|=(n-1)!\sum\limits_{i=1}^n|k-i|=(n-1)!\left(\sum_{i=1}^k(k-i)+
\sum_{i=k+1}^n(i-k)\right)= \)
\( =(n-1)!\left(\frac{k(k-1)}{2}+\frac{(n-k)(n-k+1)}{2}\right)=(n-1)!\left(\frac{n(n+1)}{2}-nk+k^2-k\right) \).
Suma noastra este \( \sum\limits_{i=1}^nS_k=(n-1)!\sum_{i=1}^n\left(\frac{n(n+1)}{2}-(n+1)k+k^2\right)= \)
\( =(n-1)!(n\frac{n(n+1)}{2}-(n+1)\frac{n(n+1)}{2}+\frac{n(n+1)(2n+1)}{6})= \)
\( =(n-1)!(\frac{n(n+1)(2n+1)}{6}-\frac{n(n+1)}{2})=(n-1)!\frac{(n-1)n(n+1)}{3}=\frac{(n-1)(n+1)!}{3} \)

Sper ca nu am gresit la calcule, dar ideea e buna, si duce la rezultatul dorit.
Poate ca exista si o alta metoda de rezolvare, dat fiind faptul ca rezultatul (acesta, daca nu e gresit) arata destul de frumos.

P.S. Pentru 2, 3 si 4 formula e adevarata, deci banuiesc ca nu am gresit la calcule.