# number of permutations with k inversions modulo 3

Let 0 ≤ k ≤ 2. Show that for n ≥ 3, the number of permutations w ∈ Sn whose number of inversions is congruent to k modulo 3 is independent of k. For instance, when n = 3 there are two permutations with 0 or 3 inversions, two with one inversion, and two with two inversions.

This is a problem from EC1 additional problems. I tried to use recursive relations:

$i(n,k)$: number of permutations in $S_n$ with exactly $k$ inversions.

$$i(n+1,k)=i(n,k)+i(n,k−1)+i(n,k−2)+⋯+i(n,k−n).$$ But it seems to be too complicated.

Any hint would be appreciated!

• Commented Sep 11, 2018 at 4:55

The generating function for the permutations by inversion is $$\sum_{\sigma\in S_n}x^{\textrm{inv}(\sigma)}=(1+x)(1+x+x^2)\cdots (1+x+x^2+\cdots+x^{n-1})$$ where $\textrm{inv}(\sigma)$ is the number of inversions of the permutation $\sigma$.
Let $f(x)=a_0+a_1x+a_2x^2+\cdots+a_m x^m$ with the $a_j$ real. Define $b_0=a_0+a_3+a_6+\cdots$, $b_1=a_1+a_4+a_7+\cdots$ and $b_2=a_2+a_5+a_8+\cdots$. Then $b_0=b_1=b_2$ iff $f(\exp(2\pi i/3))=0$.