# Number of Permutations with $k$-inversions and with a single clamped value

Let $S_n$ be the symmetric group. Recall that the number of inversions of a permutation $\sigma\in S_n$ is the number of ordered pairs $i<j$ with $\sigma(i)>\sigma(j)$. Now, call the number of permutations with $k$-inversions $I_n(k)$. It's easy to see that going from $n-1$ to $n$ we can insert $n$ into spot $j$ to add $n-j$ inversions:

$$I_n(k)=I_{n-1}(k)+I_{n-1}(k-1)+\ldots +I_{n-1}(0).$$

If we let $G_n(t)=\sum_{k=0}^{\binom{n}{2}}I_n(k)t^k$, then the above gives $G_n(t)=(1+t+t^2\ldots+t^{n-1})G_{n-1}(t)$, and it quickly follows that $G_n(t)=\prod_{j=1}^n\frac{1-x^j}{1-x}$.

I am interested in something more complicated. Let $I^{\sigma(y)=x}_n(k)$ count the number of permutations $\sigma$ of length $n$ such that for a given (fixed) $x,y$ we have $\sigma(y)=x$. In other words I am forcing $y$ to be in bin $x$. Proceeding by similar lines to the above, I get:

\begin{eqnarray*} I_n^{\sigma(y)=x}(k)&=&\ \ \ \ I_{n-1}^{\sigma(y)=x}(k)+I_{n-1}^{\sigma(y)=x}(k-1)+\ldots+I_{n-1}^{\sigma(y)=x}(n-y)\\ &&+I_{n-1}^{\sigma(y-1)=x}(k-y+2)+I_{n-1}^{\sigma(y-1)=x}(k-y+1)+\ldots+I_{n-1}^{\sigma(y-1)=x}(0) \end{eqnarray*}

where similar logic was used as before, except now we have to be careful whether we are inserting $n$ to the right/left respectively (inserting to the left shifts $x$ up one bin).

Before going on, I was hoping to confirm that the above is exactly correct with no fudges in indices.

Assuming the above is right, is it at all tractable to derive an asymptotic formula for $I_n^{\sigma(y)=x}(k)$, as $n\rightarrow\infty$?

As far as I understand, the way to derive asymptotics for $I_n(k)$, one needs something akin to the Knuth-Netto Formula:

$$I_{n}(k)=\binom{n+k-1}{k}+\sum_{j=1}^\infty (-1)^j\binom{n+k-u_j-j-1}{k-u_j-j}+\sum_{j=1}^\infty(-1)^j\binom{n+k-u_j-1}{k-u_j},$$

where the $u_j=3(3j-1)/2$ are pentagonal numbers. The above can be "simplified" using Stirling's approximation and a bunch of careful arithmetic to give asymptotics. Here is a reference for such a calculation.

Naively, the above formula comes from the Euler pentagonal number theorem. I would think one needs a specialized form of this theorem for what I am interested in.

Can such a similar asymptotic feat be accomplished for $I_n^{\sigma(y)=x}(k)$?

-
This was also posted on MO and solved there. See here. –  Hugh Thomas Sep 13 at 10:27