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