How can you count the number of permutations that have a given number of inversions?

Question

Give a permutation $S_n$, we can count the number of inversions efficiently in $O(n \log n)$ time. But given $n$ and a number of inversions $x$, is it possible to compute the number of permutations of length $n$ with $x$ inversions more quickly than brute force enumeration?

Answer 1

Let $a(n,k)$ be the number of permutations of $\{1,2,\dots,n\}$ with exactly $k$ inversions. This satisfies the recurrence and base cases \begin{align} a(n,k) &= a(n-1,k)+a(n,k-1) - a(n-1,k-n) \\ a(n,k) &= 0\text{ if $k<0$} \\ a(1,0) &= 1, \\ a(1,k) &= 0 \text{if $k\neq 0$} \end{align} These let you compute $a(n,k)$ in $O(nk)$ additions using dynamic programming. Since $k$ can be on the order of $n^2$, this is $O(n^3)$ at worst.

We can do a bit better with more sophisticated algorithms. Consider the polynomial $$ (1+x)(1+x+x^2)(1+x+x^2+x^3)\cdots (1+x+\dots+x^{n-1}) $$ It can be shown that the coefficient of $x^k$ in this polynomial is exactly $a(n,k)$, so to compute $a(n,k)$, all we have to do is compute that polynomial. The most efficient way to this is as follows. There are $n-1$ factors. Group them into pairs, possibly with one leftover, and multiply each pair using Schönhage–Strassen multiplication, which multiplies two integer polynomials of degree $d$ in $O(d\log d\log\log d)$ arithmetic operations. You now have half as many factors; repeat until there is just one factor.

On the $j^{th}$ level of this process, you will be performing $\approx n\cdot 2^{-j}$ multiplications between polynomials of degree on the order of $n\cdot 2^j$, each multiplication taking roughly $O(n\cdot 2^j\log n\log \log n)$ operations. There are $\log_2 n$ levels, so the total amount of work is $$ O(n^2(\log n)^2\log \log n) $$

Answer 2

The Wikipedia article Inversion has a link to OEIS sequence A008302

T(n,k) = number of permutations of {1..n} with k inversions.

and the generating function of it for a fixed $\,n\,$ is

$$ A_n(q) := \sum_{k\ge 0} T(n,k)\,q^k = [n]!_q := \prod_{i=1}^k \sum_{i=0}^{k-1} q^i. $$

No enumeration is needed to compute the coefficients $\,T(n,k)\,$ of polynomial $\,A_n(q).$