Determine if number of permutations is odd or even

Question

I am facing problem in this question.

Let $X$ be the total number of $n$-permutations that have exactly $k$-inversions. An inversion is defined as a pair of entries $(i,j)$ such that $i<j$ but $p(i) > p(j)$. Determine whether $X$ is odd or even.

Now, if $k$ is $0$, then $X$ is $1$ so it is odd. If $k$ is $1$, then $X$ will have just the opposite parity of $n$. But I don't know how to determine this for higher values of $k$. There isn't any explicit formula for the higher values either except for $k=2$ and $3$. I am stuck and don't know how to continue.

Answer 1

This isn't a complete answer. If $\ell(\pi)$ denotes the number of inversions of a permutation $\pi$ then

$$\sum_{\pi \in S_n} q^{\ell(\pi)} = \prod_{i=1}^n \left( q^{i-1} + \dots + q + 1 \right) = \prod_{i=1}^n \frac{q^i - 1}{q - 1}.$$

(This is the $q$-factorial $[n]_q!$; it's a nice exercise to prove this.) Working $\bmod 2$ we have that if $i = 2^k o$ where $o$ is odd then $q^i - 1 \equiv (q^o - 1)^{2^k} \bmod 2$ and applying this to every factor in the product gives

$$\prod_{i=1}^n \frac{q^i - 1}{q - 1} \equiv \prod_{1 \le 2^k o \le n, o \equiv 1 \bmod 2} \frac{(q^o - 1)^{2^k}}{q - 1} \bmod 2$$

This is admittedly still quite complicated. The number of times $o = 1$ appears in the numerator of the product is $1 + 2 + 2^2 + \dots + 2^k$ where $2^k$ is the largest power of $2$ less than or equal to $n$. In particular it is at least $n$, with equality iff $n = 2^k - 1$. That means the factors of $q - 1$ in the numerator successfully absorb the factors of $q - 1$ in the denominator, giving

$$[n]_q! \equiv (q - 1)^{2^{\lfloor \log_2 n \rfloor + 1} - 1 - n} \prod_{o \equiv 1 \bmod 2, o \ge 3} (q^o - 1)^{2^{\lfloor \log_2 \frac{n}{o} \rfloor + 1} - 1} \bmod 2.$$

In general we have

$$(x - 1)^{2^k - 1} \equiv \frac{(x - 1)^{2^k}}{x - 1} \equiv \frac{x^{2^k} - 1}{x - 1} \equiv x^{2^k - 1} + \dots + x + 1 \bmod 2$$

which gives

$$[n]_q! \equiv (q - 1)^{2^{\lfloor \log_2 n \rfloor + 1} - 1 - n} \prod_{o \equiv 1 \bmod 2, o \ge 3} \left( q^{\left( 2^{\lfloor \log_2 \frac{n}{o} \rfloor +1} - 1 \right) o} + \dots + q^o + 1 \right) \bmod 2.$$

As complicated as this looks I'm not sure it's possible to do much better, given this picture from the OEIS (this sequence is A186518) of what the Mahonian triangle $\bmod 2$ looks like (although I don't quite understand how to read it; the Mahonian triangle should have rows increasing in length quaratically...):

                                                       

Let's see what our identity says explicitly for the small-but-not-too-small example $n = 7 = 2^3 - 1$. The first factor vanishes and we get

$$[7]_q! \equiv (q^9 + q^6 + q^3 + 1)(q^5 + 1)(q^7 + 1) \bmod 2$$

(the original product had $7$ factors with $21$ terms among them; this product has $3$ factors with $8$ terms among them). This expands out to

$$\begin{align} [7]_q! &\equiv (q^9 + q^6 + q^3 + 1)(q^{12} + q^7 + q^5 + 1) \\ & \equiv (q^{21} + q^{18} + q^{15} + q^{12}) + (q^{16} + q^{13} + q^{10} + q^7) + (q^{14} + q^{11} + q^8 + q^5) + (q^9 + q^6 + q^3 + 1) \bmod 2 \end{align}$$

and in particular there is no further cancellation (this surprises me a little; I don't know whether this generalizes). So these exponents tell us which values of $k$ have the property that the number of permutations in $S_7$ with $k$ inversions is odd. Note that we really only have to compute half of these numbers because of the reflection symmetry.