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.

  • $\begingroup$ What is $I_n(x)$? $\endgroup$ – 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$.

  • $\begingroup$ Wow! This works so well. I have one last question, why is the S a sum and not a product? $\endgroup$ – Philip White Feb 20 at 3:42
  • 1
    $\begingroup$ @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.) $\endgroup$ – 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$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.