The q-factorial in terms of the major index

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.

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 *