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