Consider a permutation $\sigma$ of $[1..n]$. An inversion is defined as a pair $(i, j)$ of indices such that $i < j$ and $\sigma(i) > \sigma(j)$.

Define $A_k$ to be the number of permutations of $[1..n]$ with at most $k$ inversions.

Question: What's the tight asymptotic bound for $A_k$?

A related question was asked before: Number of permutations which have the same Kendall-Tau distance

But the question above was regarding computing $A_k$. It can be computed using dynamic programming, since it satisfies the recurrence relation shown here: https://stackoverflow.com/questions/948341/dynamic-programming-number-of-ways-to-get-at-least-n-bubble-sort-swaps

The number of permutations with exactly $k$ inversions has also been studied and it can be expressed as a generating function: http://en.wikipedia.org/wiki/Permutation#Inversions

But I can't find a closed-form formula or an asymptotic bound.

  • 2
    $\begingroup$ If you have a generating polynomial for a sequence, you can derive the generating polynomial for the prefix sums merely by multiplying the polynomial by $1/(1-x)$. In your case, you'd use the polynomial you linked to that computes the exactly-k inversions. $\endgroup$ Commented Feb 15, 2013 at 22:46
  • 2
    $\begingroup$ This is oeis.org/A161169 $\endgroup$ Commented Feb 16, 2013 at 15:33
  • 1
    $\begingroup$ @SureshVenkat Thanks for the tip. But I will still be stuck with finding the coefficient of $x^k$ in this really complicated polynomial in terms of $n$ and $k$ and I don't see how to do that. $\endgroup$ Commented Feb 16, 2013 at 17:20
  • 3
    $\begingroup$ to get the coefficient of $x^k$, take the $k$-th derivative of the generating polynomial and evaluate it at $x = 0$. $\endgroup$ Commented Feb 22, 2013 at 20:48

1 Answer 1


According to Wikipedia, the number of permutations in $S_n$ with exactly $k$ inversions is the coefficient of $X^k$ in $$1(1+X)(1+X+X^2)\cdots(1+X+\cdots+X^{n-1}).$$ Denote this by $c(n,k)$. This shows that $$c(n+1,k) = \sum_{l=0}^k c(n,k-l).$$ So the number of permutations in $S_n$ with at most $k$ inversions is equal to the number of permutations in $S_{n+1}$ with exactly $k$ inversions. This has a neat combinatorial proof as well (hint: take $\pi\in S_{n+1}$ and remove $n+1$).

If we are interested only in the coefficient of $X^k$, then factors $X^m$ for $m > k$ don't make any difference. So for $n > k$, $c(n,k)$ is the coefficient of $X^k$ in $$ \begin{align*} &1(1+X)\cdots(1+X+\cdots+X^{k-1}) (1+X+\cdots+X^k+\cdots)^{n-k} \\ = &1(1+X)\cdots(1+X+\cdots+X^{k-1}) \frac{1}{(1-X)^{n-k}} \\ = &1(1+X)\cdots(1+X+\cdots+X^{k-1}) \sum_{t=0}^\infty \binom{t+n-k-1}{t} X^t. \end{align*} $$ This implies the formula $$ c(n,k) = \sum_{t=0}^k \binom{n+t-k-1}{t} c(k,k-t), \quad n > k. $$

When $k$ is constant, the asymptotically most important term is the one corresponding to $t = k$, and we have $$ c(n,k) = \binom{n-1}{k} + O_k(n^{k-1}) = \frac{1}{k!} n^k + O_k(n^{k-1}). $$ The same asymptotics work for $c(n+1,k)$, which is what you were after.

For non-constant $k$, using the fact that $\binom{n+t-k-1}{t} = \binom{n+t-k-1}{n-k-1}$ is increasing in $t$ and $\sum_{t=0}^k c(k,t) \leq k!$, we get the bounds $$ \binom{n-1}{k} \leq c(n,k) \leq k! \binom{n-1}{k}. $$ Better bounds are surely possible, but I'll leave that to you.

  • $\begingroup$ Using Stirling's Approximation and the binomial bounds we can simplify the last expression to $c(n,k)\leq k!\binom{n-1}{k} \leq ek^{k+1/2}e^{-k}(e(n-1)/k)^k$ so $c(n,k) \leq e\sqrt{k}(n-1)^k$. This is not tight of course but it's a more elegant bound than I would expect from those approximations. $\endgroup$
    – SamM
    Commented Feb 24, 2013 at 18:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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