Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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: http://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.

share|improve this question
2  
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. –  Suresh Venkat Feb 15 '13 at 22:46
2  
This is oeis.org/A161169 –  András Salamon Feb 16 '13 at 15:33
1  
@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. –  Vinayak Pathak Feb 16 '13 at 17:20
3  
to get the coefficient of $x^k$, take the $k$-th derivative of the generating polynomial and evaluate it at $x = 0$. –  Sasho Nikolov Feb 22 '13 at 20:48

1 Answer 1

up vote 12 down vote accepted
+50

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.

share|improve this answer
    
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. –  SamM Feb 24 '13 at 18:10

Your Answer

 
discard

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.