About Warm-ups Problems News

Problem 38

Posted 08/20/2017
Refresh the webpage if formulas are not shown correctly.
Previous    Next

This problem is proposed by Ran Pan. If you want to submit your problem, please click here.


In this problem, we consider a generalized definition of inversion statistic of a permutation.

For a permutation $\pi=\pi_1\pi_2\cdots\pi_n\in\mathcal S_n$, the inversion statistic is defined as the number of pairs of elements $(\pi_i,\pi_j)$ in $\pi$ such that $i < j$ and $\pi_i > \pi_j$, say $$\mathrm{inv}(\pi)=\bigg|\{(\pi_i,\pi_j)\big|i < j,\pi_i > \pi_j\}\bigg|.$$ For example, the inversion of $\pi=416235\in\mathcal S_6$ is $6$, since the inversion pairs are $(4,1),(4,2),(4,3),(6,2),(6,3),(6,5)$.

For $k\in\mathbb{Z}^+$, we define $$\mathrm{inv}_k(\pi)=\bigg|\{(\pi_i,\pi_j)\big|i+k \leq j,\pi_i > \pi_j\}\bigg|,$$ which counts the number of inversion pairs $(\pi_i,\pi_j)$ such that the position $i$ is at least $k$ before the position $j$. For example, $\mathrm{inv}_1$ statistic is just the inversion statistic;   $\mathrm{inv}_2(416235)=4$ since the satisfying inversion pairs are $(4,2),(4,3),(6,3),(6,5)$. It is a well known result that $$ \sum_{\sigma\in\mathcal S_n} q^{\mathrm{inv}_1(\sigma)}=\sum_{\sigma\in\mathcal S_n} q^{\mathrm{inv}(\sigma)}=[n]_q ! $$

Our problem is to give a formula for $\displaystyle\sum_{\sigma\in\mathcal S_n} q^{\mathrm{inv}_2(\sigma)}.$

Back to top