Number of $n$-permutations with $r$ inversions modulo $k$ 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.
 A: 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$.
A: 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$.
