8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Why this replacement does not affect $Q$? $\endgroup$ – Fedor Petrov Dec 3 '16 at 8:38
  • $\begingroup$ 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$. $\endgroup$ – Fedor Petrov Dec 5 '16 at 14:58
  • $\begingroup$ Thanks, Fedor. In that case, we need more work for the "maj" problem. $\endgroup$ – T. Amdeberhan Dec 5 '16 at 15:00
  • $\begingroup$ Now I start to doubt that it is true for maj, please see my answer. $\endgroup$ – Fedor Petrov Dec 5 '16 at 16:56
  • $\begingroup$ Sure. We'll check then. $\endgroup$ – T. Amdeberhan Dec 5 '16 at 18:45
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Nice. Up-voted. $\endgroup$ – T. Amdeberhan Dec 3 '16 at 15:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.