TAOCP 5.1.1 Exercise 13
Let \(I_n(k)\) denote the number of permutations of \(\{1,2,\ldots,n\}\) with exactly \(k\) inversions.
Exercise 13. [M23] It is well known that half of the terms in the expansion of a determinant have a plus sign, and half have a minus sign. In other words, there are just as many permutations with an even number of inversions as with an odd number, when $n \ge 2$. Show that, in general, the number of permutations having a number of inversions congruent to $t$ modulo $m$ is $n!/m$, regardless of the integer $t$, whenever $n \ge m$.
Verified: yes
Solve time: 6m41s
Solution
Let (I_n(k)) denote the number of permutations of ({1,2,\ldots,n}) with exactly (k) inversions. From the inversion table construction (each permutation corresponds uniquely to a sequence (b_1,b_2,\ldots,b_n) with (0\le b_i<i) and (\operatorname{inv}=b_1+\cdots+b_n)), the generating function is [ G_n(z)=\sum_{k\ge0}I_n(k)z^k=\prod_{i=1}^{n}(1+z+\cdots+z^{i-1}). ] For a given integer (m\ge1) and any integer (t), we want the number [ N_{n,m,t}=\sum_{k\equiv t\pmod m}I_n(k). ] Using the roots of unity filter with (\omega=e^{2\pi i/m}), we have [ N_{n,m,t}=\frac1m\sum_{j=0}^{m-1}\omega^{-jt}G_n(\omega^j). ] Now evaluate (G_n(\omega^j)):
- For (j=0), (\omega^0=1) and (G_n(1)=\prod_{i=1}^n i = n!).
- For (1\le j\le m-1), (\omega^j\neq1). Because (n\ge m), the product for (G_n(\omega^j)) contains the factor corresponding to (i=m): [ 1+\omega^j+\cdots+(\omega^j)^{m-1}=\frac{1-(\omega^j)^m}{1-\omega^j}=0, ] since ((\omega^j)^m=1) and the denominator is non‑zero. Hence (G_n(\omega^j)=0) for all (j=1,\ldots,m-1).
Therefore [ N_{n,m,t}=\frac1m\bigl(n!+0+\cdots+0\bigr)=\frac{n!}{m}, ] which is independent of (t). The argument also covers the trivial case (m=1) (where the sum reduces to (G_n(1)=n!)). This completes the proof. ∎