Number of $n$-permutations with $r$ inversions modulo $k$

Question

So I am reading "Introduction to Enumerative and Analytic Combinatorics" and there is the following problem:

27 on page 220: Let $k \leq n-1$. How many $n$-permutations are there for which the number of inversions is $r$ mod $k$.

The solution given in the book is as follows: $n!/k$. To see this, one only has to consider the term $(1+x+...x^{k-1})$ of $I_n(x)$.

I'm confused as to why the solution in the textbook has us restricting our attention to just the $(1+x+...+x^{k-1})$ term.

Answer 1

We can consider polynomials with exponent "mod $k$". Then, your polynomial is

$$ I_n(x)=(1+x+\cdots+x^{k-1})P(x) $$

For all terms $c_sx^s$ of $P(x)$, the product $(1+x+\cdots+x^{k-1})(c_sx^s)$ is just $c_s(1+x+\cdots+x^{k-1})$, since remember the exponents are taken mod $k$. Therefore $I_n(x)$ is $S(1+x+\cdots+x^{k-1})$, where $S$ is the sum of the coefficients of $P$. Since all $k$ coefficients are equal, and they sum to $n!$ (as there are $n!$ permutations), each coefficient of $I_n(x)$ with exponents mod $k$ must be $n!/k$.

Answer 2

In general, if $A(x)=\sum_{i\ge 0}a_ix^i$ is a polynomial, and $\zeta$ is a primitive $k^{th}$ root of unity, then the sum of the coefficients of $A$ whose indices are congruent to $r\pmod k$ is $$ \sum_{i\ge 0} a_{r+ik}=(A(1)+\zeta^rA(\zeta)+\zeta^{2r}A(\zeta^2)+\dots+\zeta^{(k-1)r}A(\zeta^{k-1}))/k. $$ Since $I_n(x)$ has a factor of $(1+x+x^2+\dots+x^{k-1})=\frac{1-x^k}{1-x}$ for $x\neq 1$, all of the terms $\zeta^{jr}A(\zeta^j)$ for $i\le j \le k-1$ are zero, and the above is equal to $I_n(1)/k=n!/k$.