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

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!

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