Number of permutations of $[n]$ with a multiple of $n$ inversions

Question

We have a permutation $\left(a_1,a_2,...,a_n\right)$ of the set $\{1,2,...,n\}$. A pair $(a_i,a_j)$ is said to be an inversion of this permutation if $i<j$ and $a_i>a_j$. Find the number of permutations for which the number of all inversions is divisible by $n$.

Answer 1

HINT: Let $a_n$ be the number of permutations of $[n]$ having a multiple of $n$ inversions. If $b_{n,k}$ is the number of permutations of $[n]$ with exactly $k$ permutations, we have the generating function

$$\sum_{k=0}^{\binom{n}2}b_{n,k}x^k=(1)(1+x)(1+x+x^2)\ldots(1+x+\ldots x^{n-1})\;.$$

From this it’s not hard to calculate the following values of $a_n$ by hand:

$$\begin{array}{rcc} n:&1&2&3&4&5&6\\ a_n:&1&1&2&6&24&120 \end{array}$$

That very strongly suggests a certain conjecture, and that conjecture has a rather simple combinatorial proof. I’ve put the key idea for the combinatorial proof in the spoiler-protected block below; mouse-over to see it.

Let $\pi$ be a permutation of $[n]$. There is exactly one place to insert $n+1$ into $\pi$ to get a permutation of $[n+1]$ that has a number of inversions divisible by $n+1$.