About Warm-ups Problems News

Problem 39

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 generalize our definition in Problem 38.

We continue our definition in Problem 38, and for $k,l\in\mathbb{Z}^+$, we define $$\mathrm{inv}_{k,l}(\pi)=\bigg|\{(\pi_i,\pi_j)\big|i+k \leq j,\pi_i \geq \pi_j+l\}\bigg|,$$ which only counts the number of inversion pairs $(\pi_i,\pi_j)$ such that the position $i$ is at least $k$ before the position $j$ and $\pi_i$ is at least $l$ greater than $\pi_j$. For example, $\mathrm{inv}_{2,2}(416235)=2$ since the satisfying inversion pairs are $(4,2),(6,3)$.

The statistics $\mathrm{inv}_{k,l}$ is not necessarily equal to $\mathrm{inv}_{l,k}$. for example, $\mathrm{inv}_{2,1}(1764253)=0+4+3+1+0+0+0=8$ while $\mathrm{inv}_{1,2}(1764253)=0+4+3+1+0+1+0=9.$ However, it is not too hard to see that $\mathrm{inv}_{k,l}$ and $\mathrm{inv}_{l,k}$ are distributively equivalent on $\mathcal S_n$ (by inversing map), i.e. $$\sum_{\sigma\in\mathcal S_n} q^{\mathrm{inv}_{k,l}(\sigma)}=\sum_{\sigma\in\mathcal S_n} q^{\mathrm{inv}_{l,k}(\sigma)}.$$

Find a formula for $\displaystyle\sum_{\sigma\in\mathcal S_n} q^{\mathrm{inv}_{k,l}(\sigma)}$ for any $k \geq l > 0$.

Back to top