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

Question

This question is cross-posted from math.stackexchange because it might be too technical.

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:

$$I_{n}^{\sigma(y)=x}(k)=\sum_{i=0}^{n-1-y}I_{n-1}^{\sigma(y)=x}(k-i)+\sum_{i=n-y+1}^nI^{\sigma(y-1)=x}_{n-1}(k-i)$$

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

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)$?

Answer 1

It follows from the Knuth-Netto formula that the asymptotics of $I_n(k)$, for $k$ fixed, is $n^k/k!$ to first order.

I claim the asymptotic behaviour of $I_n^{\sigma(y)=x}(k)$ is as $n^{k-|x-y|}/(k-|x-y|)!$.

For convenience I am going to assume that $x\geq y$. The other case can be treated the same way.

First, we construct a set of permutations of the desired order inside $I_n^{\sigma(y)=x}(k)$. Consider permutations such that

• $\sigma(j)=j$ for $1\leq j\lt y$,
• $\sigma(y)=x$,
• $\sigma(j)=j-1$ for $y+1\leq j \leq x$.

I.e., I have fixed the behaviour of the permutation on $1,\dots,x$, and this has introduced $x-y$ inversions. Now determine the rest of $\sigma$ by choosing an arbitrary permutation on $x+1,\dots,n$ with $k-(x-y)$ inversions. This gives us enough permutations in $I_n^{\sigma(y)=x}(k)$.

Now we show that there are no more than this many (to first order).

It's helpful to think of permutations of $n$ as planar matchings between a top row of $n$ dots and a bottom row of $n$ dots. Then inversions are just points where two arcs cross. (We assume the diagram is drawn in a sensible way so three arcs don't cross at a point, and arcs which don't need to cross, don't cross.)

When looking at permutations which satisfy that $\sigma(y)=x$, we have fixed one arc. If we erase that arc, the resulting diagram has $n-1$ dots left on top and bottom, so it can be viewed as a permutation in $S_{n-1}$.

Suppose we take a permutation in $I_n^{\sigma(y)=x}(k)$ and remove the arc from $y$ to $x$. This arc must be crossed by at least $x-y$ arcs (because it has that many more starting points than ending points to its right). Therefore, erasing this arc removes at least $x-y$ inversions. Thus, we get an injective map $$I_n^{\sigma(y)=x}(k) \rightarrow I_{n-1}(k-(x-y)) \cup I_{n-1}(k-(x-y)-1) \dots .$$

By the asymptotics already mentioned, the second and later terms on the RHS are lower order, and the first term has the desired asymptotics. This shows that the claimed formula is an upper bound to first order as well.