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.

• What is $I_n(x)$? – Peter Taylor Feb 20 at 16:00

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

• Wow! This works so well. I have one last question, why is the S a sum and not a product? – Philip White Feb 20 at 3:42
• @PhilipWhite Well, for example, try $(a+bx+cx^2)(1+x+x^2)$ with exponents mod $3$. (Although note that my $P(x)$ is the product of all $(1+x+\cdots+x^{j-1})$s with $1\le j\le n$ and $j\ne k$, if that's what you meant.) – arctic tern Feb 20 at 3:53

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

• Can you explain what is $P(x)$ and $I_n(x)$, what are they counting – reuns Feb 20 at 20:23
• @reuns I never mentioned $P(x)$, did you intend to comment on the other answer? – Mike Earnest Feb 20 at 20:55
• What those polynomials are counting – reuns Feb 20 at 22:14