## Problem 39

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

----------------------

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