# factorization of polynomials wrt the major index stat

Let $\mathfrak{S}_n$ be the permutation group on $\{1,\dots,n\}$. Given $\pi=\pi_1\pi_2\dots\pi_n\in\mathfrak{S}_n$, its major index statistic is denoted maj$(\pi)$. Define the polynomials $$Q_{n,k}(x):=\sum_{\pi\in\mathfrak{S}_n}x^{\text{maj}(\pi)+\pi_n+\pi_{n-1}+\cdots+\pi_{n-k}}.$$

EDIT.

maj can be replaced by the inversion number inv without affecting $Q$. This is true due to the work of Foata and Schutzenberger on the equi-distribution of the two statistics (as multisets). However, Fedor's question made me reflect again. Is it still true that $\{\text{maj$(\pi)+\pi_n+\dots+\pi_{n-k}$}: \pi\in\mathfrak{S}_n\}$ and $\{\text{inv$(\pi)+\pi_n+\dots+\pi_{n-k}$}: \pi\in\mathfrak{S}_n\}$ are equi-distributed? If yes, then Fedor's answer is complete.

CLAIM. $\,\,$ Experiment supports that, for each $n$ and $k$, we have $$Q_{n,k}(x) =\binom{n}{k+1} x^{(k+1)n-\binom{k+1}2}\prod_{i=0}^k\left(1+x+\cdots+x^i\right)\prod_{j=0}^{n-k-2}\left(1+x+\cdots+x^j\right).$$ Any proof?

The above exploration was motivated by this paper.

• Why this replacement does not affect $Q$? Dec 3, 2016 at 8:38
• For $k=1$ even the common distribution of $(maj,\pi_n)$ is the same as a common distribution of $(inv,\pi_n)$. For $k=2$ the common distribution of $(maj,\pi_{n-1}+\pi_n)$ is not already the same as a common distribution of $(inv,\pi_{n-1}+\pi_n)$, which may be seen from the case $\pi_{n-1}+\pi_n=2n-1$. Dec 5, 2016 at 14:58
• Thanks, Fedor. In that case, we need more work for the "maj" problem. Dec 5, 2016 at 15:00
• Now I start to doubt that it is true for maj, please see my answer. Dec 5, 2016 at 16:56
• Sure. We'll check then. Dec 5, 2016 at 18:45

For inv instead of maj this is rather clear. I claim that when we fix a $(k+1)$-element subset $K$ of $\{1,2,\ldots,n\}$, the polynomial $$\sum_{\pi}x^{\operatorname{inv}(\pi)+\pi_n+\pi_{n-1}+\cdots+\pi_{n-k}} ,$$ where the sum is running over the $\pi\in\mathfrak{S}_n$ with $\{\pi_{n-k},\dots,\pi_n\} = K$, equals $$x^{(k+1)n-\binom{k+1}2}\prod_{i=0}^k\left(1+x+\cdots+x^i\right)\prod_{j=0}^{n-k-2}\left(1+x+\cdots+x^j\right).$$
Indeed, let us count the number of inversions $(\pi_m<\pi_j)$ for which $j<n-k\leqslant m$. For fixed $m$ the number of such inversions equals $n-\pi_m-|i\geqslant n-k:\pi_i>\pi_m|$. When we sum up by all $m=n-k,\dots,n$, we get $n(k+1)-\sum_{m\geqslant n-k} \pi_m-\binom{k+1}2$. So, $\operatorname{inv}(\pi)+\sum_{m\geqslant n-k} \pi_m$ equals $n(k+1)-\binom{k+1}2$ plus the number of inversions inbetween first $n-k-1$ elements plus the number of inversions inbetween last $k+1$ elements. These are independent and have known generating polynomials $\prod_{i=1}^s(1+x+\dots+x^{i-1})$, for $s=n-k-1$ or $s=k+1$ respectively. Thus the result.
I doubt that for maj it is true, please recheck. It should not be divisible by such a high power of $x$, since it may appear that maj is small, say, maj$=n-k-1$, and $\{\pi_{n-k},\dots,\pi_n\}=\{1,2,\dots,k+1\}$.