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

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$.

• This is the same as the number of compositions $(i_1,i_2,\ldots,i_{n-1})$ such that $0\leq i_j\leq j$ and $n|\sum_{j}{i_j}$. Do you need a closed formula for that? Commented Jan 25, 2015 at 15:46

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$.

• So basicly said, the asnwer is $(n-1)!$? Commented Jan 25, 2015 at 16:44
• @SoulEater: That’s right. With a fairly easy combinatorial proof. Commented Jan 25, 2015 at 16:45
• Well, since I am a highschooler not everything is clear to me, could you please simplify it? Commented Jan 25, 2015 at 16:46
• @SoulEater: Let $\pi=(p_1\ldots p_n)$ be any permutation of $[n]$. We’re going to insert $n+1$ into it and try to get a permutation with a multiple of $n+1$ inversions. After I insert $n+1$, the new permutation will have all of the inversions of $\pi$ plus the new ones involving $n+1$. There will be exactly as many of those as there are $p_k$’s after $n+1$. That number can be anywhere from $0$, if we tack $n+1$ on at the end of $\pi$, to $n$, if we put it at the beginning. Suppose that $\pi$ has $m$ inversions. There’s exactly one $r$ with $0\le r\le n$ such that $n+1\mid m+r$, so there’s ... Commented Jan 25, 2015 at 16:54
• ... exactly one way to extend $\pi$ to a permutation of $[n+1]$ with a multiple of $n+1$ inversions. Thus, $a_{n+1}=n!$, and $a_n=(n-1)!$. Commented Jan 25, 2015 at 16:55