The q-factorial in terms of the major index

EDIT: As pointed out in the comments, the following proof is found in Knuth’s book, The Art of Computer Programming, Vol. 3, and is attributed to MacMahon.

There are several nice series expansions involving basic permutation statistics which I’ve been reviewing lately. One of these involves the number of inversions of a permutation.

An inversion of a permutation of the numbers $1,2,\ldots,n$ is a pair of numbers which appear ``out of order’’ in the sequence, that is, with the larger number appearing first. For instance, for $\DeclareMathOperator{\maj}{maj} \DeclareMathOperator{\inv}{inv} n=4$, the permutation $3,1,4,2$ has three inversions: $(3,1)$, $(3,2)$, and $(4,2)$. We write \[\inv(3142)=3.\]

It is not hard to show that \[(1)(1+q)(1+q+q^2)\cdots(1+q+q^2+\cdots+q^{n-1})=\sum q^{\inv(w)}\] where the sum ranges over all permutations $w$ of $\{1,2,\ldots,n\}$. (See bottom of this post for a proof.) The product on the left side is called the $n$th $q$-factorial.

The remarkable thing is that there is a similar expansion of the $q$-factorial in terms of the major index. Define a descent of a permutation to be an index $i$ for which the $i$th number is greater than the $(i+1)$st. The major index is defined to be the sum of the descents. For instance, the permutation $3,1,4,2$ has two descents, in positions $1$ and $3$, so the major index is $4$. We write \[\maj(3142)=4.\]

With this notation, we have \begin{equation}(1)(1+q)(1+q+q^2)\cdots(1+q+q^2+\cdots+q^{n-1})=\sum_{w\in S_n} q^{\maj(w)}\end{equation} as well, implying that the number of permutations with $k$ inversions is equal to the number of permutations with major index $k$, for any $k$. There is a direct bijection showing this called the Foata bijection.

I was seeking a way to prove equation (1) directly, without the Foata bijection. But the simplest proof I was able to find in the literature, in Stanley’s Enumerative Combinatorics, proved it by showing something much more general and then simply stating it as a corollary. Wishing to see a direct proof of the result, I went through Stanley’s more general proof step-by step to see what was going on in this special case. I thought I would share it here since I had a hard time finding it elsewhere.

We first rewrite each $\DeclareMathOperator{\maj}{maj} \DeclareMathOperator{\inv}{inv} 1+q+q^2+\cdots+q^i$ as $\frac{1-q^i}{1-q}$ so that the equation becomes \[\frac{1}{(1-q)^n}=\frac{\sum_{w\in S_n} q^{\maj (w)}}{(1-q)(1-q^2)\cdots(1-q^n)}.\]

The left hand side is the generating function for compositions of a given size having $n$ nonnegative integer parts. (For instance, $(3,0,2,2)$ is a composition of $7$ having $4$ parts.) The right hand side is a product of two generating functions: $\sum_{w\in S_n} q^{\maj (w)}$ enumerates the number of permutations having a given major index, and $\frac{1}{(1-q)(1-q^2)\cdots(1-q^n)}$ enumerates the number of partitions of a given size into parts of size $1,2,\ldots,n$.

So, it suffices to find a bijection $\phi$ from the set of compositions $\sigma$ having $n$ parts and size $N$ to the set of pairs $(\lambda,\pi)$ of partitions $\lambda$ using parts $1,\ldots,n$ and permutations $\pi$ of $1,\ldots,n$ such that $|\lambda|+\maj(\pi)=N$.

We illustrate this bijection with an example, which will make the construction clear. Suppose $\sigma=(5,1,0,2,3,0)$, so that $n=6$ and $N=11$. We let $\pi$ be the unique permutation that puts the entries of $\sigma$ in decreasing order, where ties are put in left-to-right order. So, in this case $\pi$ is the permutation $154236$, since then $(\sigma_{\pi(1)},\ldots,\sigma_{\pi(6)})=(5,3,2,1,0,0)$ where the $0$’s from positions $3$ and $6$ of $\sigma$ give the $3$ and $6$ in increasing order at the end of $\pi$.

Now that we have $\pi$ and the re-ordered version of $\sigma$, whose entries we will call $a_1,\ldots,a_6$ ($=(5,3,2,1,0,0)$), we construct a partition $\lambda$ as follows. We first construct integers $c_1,\ldots,c_6$ such that, for each $i$, if $\pi(i)<\pi(i+1)$ then $c_i=a_i-a_{i+1}$, and if $\pi(i)>\pi(i+1)$ then $c_{i}=a_i-a_{i+1}-1$. So in this case $(c_1,\ldots,c_6)=(2,0,0,1,0,0)$. Notice that we took consecutive differences but subtracted an extra $1$ for each descent of $\pi$.

Appendix: Here is a proof of the formula \[\DeclareMathOperator{\maj}{maj} \DeclareMathOperator{\inv}{inv} (1)(1+q)(1+q+q^2)\cdots(1+q+q^2+\cdots+q^{n-1})=\sum q^{\inv(w)}.\]

Proof: If we form one of the summands in the expansion above by choosing one power of $q$ from each factor above from left to right, we can construct the corresponding permutation $w$ as follows. Starting with the $1$ from the first factor, write down the number $\mathbf{1}$. For the second factor, we can either choose $1$ or $q$. If we choose $1$, we write the number $\mathbf{2}$ to the right of the $\mathbf{1}$, and if we choose the $q$ then we write $\mathbf{2}$ to the left of the $\mathbf{1}$ so that there is one inversion so far. We continue in this manner, such that if we pick $q^r$ from the $i$th factor, we write $\mathbf{i}$ in the unique position among the letters $\mathbf{1},\ldots,\mathbf{i-1}$ such that it precedes exactly $r$ of the letters already written, hence forming $r$ new inversions. This process forms a permutation $w$ with the correct number of inversions.