Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
This was also posted on MO and solved there. See here. – Hugh Thomas Sep 13 '13 at 10:27
@HughThomas: Would you consider posting it as an answer here too (or at least a link to that answer), so that this question no longer shows up as "unanswered"? – ShreevatsaR Jan 20 '14 at 8:41

At the request of ShreevatsaR commenting above, I have copied my answer from MO below.

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.