# The r-major index

In order to prove they are all equidistributed, it suffices to show that for any $r\ge 1$, we have $$\sum_{\pi\in S_n} q^{r\text{-maj}(\pi)}=(n)_q!=(1+q)(1+q+q^2)\cdots (1+q+q^2+\cdots + q^{n-1}).$$ It is easy to see that the $q$-factorial $(n)_q!$ can also be defined by the recursion $$(n)_q!=(1+q+q^2+\cdots+q^{n-1})\cdot (n-1)_q!,$$ with initial condition $(1)_q!=1.$ Thus it suffices to show that the generating function $$F_n(q)=\sum_{\pi\in S_n} q^{r\text{-maj}(\pi)}$$ also satisfies this recursion.

Clearly $F_1(q)=1$, since there is one permutation of $1$ and it has no inversions or descents of any type. Now for the recursion: we want to show $$F_n(q)=(1+q+q^2+\cdots +q^{n-1})\cdot F_{n-1}(q),$$ which is combinatorially equivalent to finding a way of producing, from a permutation $\pi\in S_{n-1}$, a collection of $n$ permutations $a_0(\pi),a_1(\pi),\ldots,a_{n-1}(\pi)$ in $S_n$ such that $r\text{-maj}(a_i(\pi))-r\text{-maj}(\pi)=i$ for all $i$, and such that every permutation in $S_n$ occurs exactly once among the $a_i(\pi)$’s.

To do so, consider a permutation $\pi\in S_{n-1}$. For instance, if $n=8$, we might have $\pi=5246731$, and $r=3$. We will form each of $a_0(\pi),\ldots,a_{n-1}(\pi)$ by inserting an $n$ (in this case $8$) between two of the elements of $\pi$ to form a partition in $S_n$. To make our construction clear, let us underline the numbers $1,\ldots,n-r$ in $\pi$, and boldface the $r$-descents, in this case:
$$\underline{\mathbf{5}}\, \underline{2}\,\underline{4}\,6\,\mathbf{7}\,\underline{3}\,\underline{1}$$
The underlined numbers are those for which, if the $n$ was inserted just to its left, it would create a new $r$-descent (and possibly break one existing $r$-descent with that entry). The non-underlined numbers are those which the $n$ can make new $r$-inversions with.

If we insert the $n$ at the end of the sequence, it does not add descents or inversions and so does not change the $r$-maj; we therefore define $a_0(\pi)$ to be the permutation formed by inserting the $n$ at the end of $\pi$.

Now, consider the gaps that are either (a) just preceding a number which is not underlined, or (b) just after an $r$-descent, as shown by the arrows:
$$\begin{array}{cccccccccccccc} & \underline{\mathbf{5}} & & \underline{2} & & \underline{4} & & 6 & & \mathbf{7} & & \underline{3} & & \underline{1} & \\ & &\uparrow & & & &\uparrow & &\uparrow & &\uparrow & & & & \end{array}$$

Suppose there are $t$ such gaps, of type (a) or (b). If the $n$ is inserted in the rightmost such gap, it would add $1$ to the $r$-maj, since either it would form a new $r$-inversion (if the gap was type (a)) or shift the rightmost $r$-descent’s location over by $1$ (if type (b)). Since none of the non-underlined entries can be the smaller entry of an $r$-descent, no gap can be simultaneously of type (a) and (b). Thus as we move to the left along these gaps, each either successively adds an extra $r$-inversion or shifts over another $r$-descent (in addition to those already formed or shifted to its right). It follows that the $r\text{-maj}$ would increase by $i$ when inserting the $n$ in the $i$th such gap from the right:

$$\begin{array}{cccccccccccccc} & \underline{\mathbf{5}} & & \underline{2} & & \underline{4} & & 6 & & \mathbf{7} & & \underline{3} & & \underline{1} & \\ & &\uparrow & & & &\uparrow & &\uparrow & &\uparrow & & & & \uparrow \\ & &\small 4 & & & &\small 3 & &\small 2 & &\small 1 & & & & \small 0 \end{array}$$

and so we define $a_i(\pi)$ accordingly for $1\le i\le t$.

As for the remaining gaps, we claim that labeling them from left to right now will increase the difference by $1$ each time, starting from $t+1$. Indeed, in all other gaps the $n$ will form a new descent, with a value of $1$ in the leftmost column added to the same number of new $r$-inversions and shifted $r$-descents as for the gap of $a_t$. As we move it to the right, the position will dictate both how many of those $r$-inversions and shifted $r$-descents are undone, and the value contributed by the new $r$-descent that $n$ forms. This will have the effect of adding one each time, and so our gaps contribute differences as follows:

$$\begin{array}{cccccccccccccc} & \underline{\mathbf{5}} & & \underline{2} & & \underline{4} & & 6 & & \mathbf{7} & & \underline{3} & & \underline{1} & \\ \uparrow & &\uparrow & &\uparrow & &\uparrow & &\uparrow & &\uparrow & & \uparrow & & \uparrow \\ \small 5 & &\small 4 & &\small 6 & &\small 3 & &\small 2 & &\small 1 & & \small 7 & & \small 0 \end{array}$$

We define the remaining $a_i(\pi)$’s accordingly. Note that this correspondence is reversible, since we can recover $\pi$ from any $a_i(\pi)$ by simply removing the entry $n$. This completes the proof!