<p>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$).</p>

<p>If we are interested only in the coefficient of $X^k$, then factors $X^m$ for $m &gt; k$ don't make any difference. So for $n &gt; k$, $c(n,k)$ is the coefficient of $X^k$ in
$$
\begin{align*}
&amp;1(1+X)\cdots(1+X+\cdots+X^{k-1}) (1+X+\cdots+X^k+\cdots)^{n-k} \\ =
&amp;1(1+X)\cdots(1+X+\cdots+X^{k-1}) \frac{1}{(1-X)^{n-k}} \\ =
&amp;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 &gt; k.
$$</p>

<p>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. </p>

<p>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.</p>

CC BY-SA 3.0
2013-02-24T18:10:32.310Z
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
CC BY-SA 3.0
2013-02-23T04:40:36.987Z
2013-02-23T04:54:38.333Z
2013-02-23T04:54:38.333Z
Yuval Filmus
<p>Consider a permutation $\sigma$ of $[1..n]$. An inversion is defined as a pair $(i, j)$ of indices such that $i &lt; j$ and $\sigma(i) &gt; \sigma(j)$.</p>

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

<p>Question: What's the tight asymptotic bound for $A_k$?</p>

<p>A related question was asked before: <a href="https://cstheory.stackexchange.com/questions/10686/number-of-permutations-which-have-the-same-kendall-tau-distance">Number of permutations which have the same Kendall-Tau distance</a></p>

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

<p>The number of permutations with <em>exactly</em> $k$ inversions has also been studied and it can be expressed as a generating function: <a href="http://en.wikipedia.org/wiki/Permutation#Inversions" rel="nofollow noreferrer">http://en.wikipedia.org/wiki/Permutation#Inversions</a></p>

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

CC BY-SA 3.0
2013-02-15T22:46:37.160Z
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
CC BY-SA 3.0
2013-02-16T15:33:04.997Z
This is http://oeis.org/A161169
András Salamon
CC BY-SA 3.0
2013-02-16T17:20:58.143Z
@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
CC BY-SA 3.0
2013-02-22T20:48:29.160Z
to get the coefficient of $x^k$, take the $k$-th derivative of the generating polynomial and evaluate it at $x = 0$.
Sasho Nikolov
<co.combinatorics><permutations>
Asymptotically, how many permutations of $[1..n]$ have at most $k$ inversions?
Vinayak Pathak
# Asymptotically, how many permutations of $[1..n]$ have at most $k$ inversions?

(Asked by: username_0 on 2013-02-15)

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](https://cstheory.stackexchange.com/questions/10686/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.

**Tags:** co.combinatorics, permutations
> **Comments:**
> **username_1**: 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.  
> **username_2**: This is http://oeis.org/A161169  
> **username_0**: @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.  
> **username_3**: to get the coefficient of $x^k$, take the $k$-th derivative of the generating polynomial and evaluate it at $x = 0$.  

---

## 1 answers

### Answer by username_4 on 2013-02-23. Score: 12 | Accepted answer

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.

> **Comments:**
> **username_5**: 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.  

---

