The q-factorial in terms of the major index

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

Finally, let $\lambda$ be the partition having $c_i$ parts of size $i$ for each $i$. So in this case $\lambda=(4,1,1)$. Then $|\lambda|=6$ and $\maj(\pi)=2+3=5$, so $|\lambda|+\maj(\pi)=11=|\sigma|$ as desired. QED!

2 thoughts on “The q-factorial in terms of the major index

  1. This proof can also be found in Knuth’s The Art of Computer Programming Vol.3 5.1.1, where it is attributed to MacMahon.

Leave a Reply

Your email address will not be published. Required fields are marked *