Question about element in $\{1,\cdots,n\}$ and its product with its permutation: $\sum_{j=1}^nj\sigma(j)$ for $\sigma \in S_n$ [closed]

Question

Let $\sigma\in S_n$ for some $n\in \mathbb{N}$. I am interested in $\displaystyle \sum_{j=1}^nj\sigma(j)$. Can anyone help point me in a decent direction? If $\sigma = (1)$ in cycle notation, we have that the sum just becomes $\frac{n(n+1)(2n+1)}{6}$. Now for the fun part, I actually want to look at this sum for all of the permutations in $S_n$. We can brute force this for small $n$, but it quickly gets out of hand.

Answer 1

I am assuming you mean the sum over all $\sigma$ of the sum you wrote. (If you meant you want to investigate the sum you wrote for specific individual $\sigma$, that's different.)

So... reversing the sum, $$\sum_{\sigma\in S_n}\sum_{j=1}^n j\sigma(j)=\sum_{j=1}^n\sum_{\sigma\in S_n} j\sigma(j)\ .$$ The inner sum has $n!$ terms, and among those terms, each value $\sigma(j)=1,2,\ldots,n$ occurs $(n-1)!$ times. So $$\eqalign{\sum_{j=1}^n\sum_{\sigma\in S_n} j\sigma(j) &=\sum_{j=1}^nj(1+2+\cdots+n)(n-1)!\cr &=(1+2+\cdots+n)^2(n-1)!\cr &=\frac{n^2(n+1)^2}{4}(n-1)!\ .\cr}$$