10-permutations with exactly 4 inversions

Question

Let $p = p_1p_2\dots p_n$ A pair of elements $(p_i,p_j)$ is called an inversion in p if i > j and $p_i < p_j $.

Now, I know that the generating function for 10-permutations with k inversions is $I_{10}=(1+x)(1+x+x^2)\dots (1+x+\dots +x^9) $ where the coefficient of $x^4$ is the number I'm looking for, however, I do not want to expand this product because I think there must be a cleaner way to do it.

Answer 1

There are not so many ways to write $4$ as a sum of positive natural numbers (just $1+1+1+1,2+1+1,2+2,3+1,4$), so to compute the coefficient of $x^4$ in $$(1+x)(1+x+x^2)\cdot\ldots\cdot(1+x+x^2+\ldots+x^9)$$ is far from being a nightmare.
According to this insightful paper, the answer you are looking for is $\color{red}{\large 440}$.
It can be checked with the Mathematica command $$\text{SeriesCoefficient}\left[\prod _{k=1}^9 \sum _{j=0}^k x^j,\{x,0,4\}\right]$$ and matches with $$\underbrace{\binom{9}{4}}_{1+1+1+1}+\underbrace{8\cdot\binom{8}{2}}_{2+1+1}+\underbrace{\binom{8}{2}}_{2+2}+\underbrace{7\cdot 8}_{3+1}+\underbrace{6}_{4}.$$

Answer 2

As pointed out by @Jack D'Aurizio, it's not that hard to compute the coefficient of $x^4$ in the generating function.

We have $$\begin{aligned}I_{10} &= (1+x)(1+x+x^2)(1+x+x^2+x^3) \cdots (1+x+\dots +x^9) \\ &= \frac{1-x^2}{1-x} \cdot \frac{1-x^3}{1-x} \cdot \frac{1-x^4}{1-x} \cdots \frac{1-x^{10}}{1-x} \\ &= (1-x^2)(1-x^3)(1-x^4) \cdots (1-x^{10}) (1-x)^{-9} \\ &= (1-x^2)(1-x^3)(1-x^4) \cdots (1-x^{10}) \sum_{i=0}^{\infty} \binom{9+i-1}{i} x^i \\ \end{aligned}$$ There are only a few ways the exponents in this expression can add up to $4$: $0+4 =2+2=3+1=4+0$. So $$[x^4]I_{10} = \binom{9+4-1}{4} - \binom{9+2-1}{2} - \binom{9+1-1}{1} - \binom{9+0-1}{0} = 440$$

Answer 3

We can begin by looking for the first $n$ where we start getting some $4\text{-inversions}$ in the $n\text{-permutations}$ group and using the generating function we quickly write out that the 'action' begins at $n = 4$:

$$ (1 + x) (1 + x + x^2) (1 + x + x^2 + x^3) = x^6 + 3 x^5 + 5 x^4 + 6 x^3 + 5 x^2 + 3 x + 1$$

Now when you think about multiplying this polynomial with $1 + x + x^2 + x^4$ to find the $x^4$ coefficient for $n =5$ you see that you can manually crank-out the answer by ignoring the higher order powers and collecting what you need at each step of $4$ additions going into an accumulator (right to left calculations).

And you can go on in this fashion step by step:

$ n \quad \text{5-tuple}$
$ 4 \quad 5,\;6,\;5,\;3,\;1$
$ 5 \quad 5+6+5+3+1,\;6+5+3+1,\;5+3+1,\;3+1,\;1$
$ 5 \quad 20,\;15,\;9,\;4,\;1$
$ 6 \quad 49,\;29,\;14,\;5,\;1$
$ 7 \quad 98,\;49,\;20,\;6,\;1$
$ 8 \quad 174,\;76,\;27,\;7,\;1$
$ 9 \quad 285,\;111,\;35,\;8,\;1$
$ 10 \quad 440,\;155,\;44,\;9,\;1$

and so there are $440$ permutations of $\{1,2,3,4,5,6,7,8,9,10\}$ with exactly $4$ inversions.

The mental work involved here was calculating $24$ accumulating additions.