How to find the number of $2$ inversions in $S_5$?

Question

How would I find the number of permutations in $S_5$ that have exactly $2$ inversions?

By inversion I mean if $i<j$ but $\sigma(i)>\sigma(j)$ i.e the order in which an element appears is switched in the permutation.

I have found the following $6$

$$\begin{pmatrix} 1 & 2 & 3 & 4 & 5\\ 1 & 2 & 5 & 3 &4 \end{pmatrix}$$

$$\begin{pmatrix} 1 & 2 & 3 & 4 & 5\\ 1 & 4 & 2 & 3 &5 \end{pmatrix}$$

$$\begin{pmatrix} 1 & 2 & 3 & 4 & 5\\ 3 & 1 & 2 & 4 &5 \end{pmatrix}$$

simply by pulling the element $5$ back two places and then $4$ back two places and then the same for $3$. This no longer works with $2$ because we have to move it to $5$ and this gives more than two inversions however we can reverse it and move $1$ forward two places and then move $2$ forward two places and likewise for $3$ this gives.

$$\begin{pmatrix} 1 & 2 & 3 & 4 & 5\\ 2 & 3 & 1 & 4 &5 \end{pmatrix}$$

$$\begin{pmatrix} 1 & 2 & 3 & 4 & 5\\ 1 & 3 & 4 & 2 &5 \end{pmatrix}$$

$$\begin{pmatrix} 1 & 2 & 3 & 4 & 5\\ 1 & 2 & 4 & 5 &3 \end{pmatrix}$$

this gives us $6$ permutations with only $2$ inversions.

Is this all? Can anyone show me a better way that just trying to figure them out?

Thanks!

Answer 1

The generating function for inversions is the factorial $q$-analogue

$$\left[n\right]_q!$$

The $q$-analogue of $k$ is

$$\left[k\right]=1+q+q^2+q^3+\cdots +q^{k-1}$$

so the factorial $q$-analogue is

$$\left[n\right]_q!=1(1+q)(1+q+q^2)(1+q+q^2+q^3)\cdots (1+q+q^2+q^3+\cdots +q^{n-1})$$

The number of permutations with $k$ inversions is given by the $x^k$ coefficient $A_{n,k}$ of

$$\left[n\right]_q! = \sum_{k=0}^{\binom{n}{2}}A_{n,k}x^k$$

in your case you want $A_{5,2}$.

There is a simple proof of this inversion generating function in Theorem 1.2 page 3 of this book

Multiplying these polynomials is either a job for a computer algebra system like sage or we can do it manually.

In sage if we input

show(expand(1*(1+x)*(1+x+x^2)*(1+x+x^2+x^3)*(1+x+x^2+x^3+x^4)))

we get the output

$$x^{10} + 4 \, x^{9} + 9 \, x^{8} + 15 \, x^{7} + 20 \, x^{6} + 22 \, x^{5} + 20 \, x^{4} + 15 \, x^{3} + 9 \, x^{2} + 4 \, x + 1$$

which gives 9 as your answer.

Edit: The full list of permutations with $2$ inversions. I have highlighted all occurrences of a larger number occurring to the left of a smaller. The ones accounted for in the question are checked $\checkmark$.

$$\begin{array}{c}\text{Permutations}\\ \begin{array}{|ccccc|c|}\hline \boxed{2} & \boxed{3} & 1 & 4 & 5 &\checkmark\\ \boxed{2} & 1 & \boxed{4} & 3 & 5&\\ \boxed{2} & 1 & 3 & \boxed{5} & 4&\\ 1 & \boxed{3} & \boxed{4} & 2 & 5&\checkmark\\ 1 & \boxed{3} & 2 & \boxed{5} & 4&\\ 1 & \boxed{4} & 2 & 3 & 5&\checkmark\\ 1 & 2 & \boxed{4} & \boxed{5} & 3&\checkmark\\ 1 & 2 & \boxed{5} & \boxed{3} & 4&\checkmark\\ \boxed{3} & 1 & 2 & 4 & 5&\checkmark\\\hline \end{array}\end{array}$$

Answer 2

We can quickly get the answer to this exam problem using the technique found here.

$$\tag 1 (1 + x) (1 + x + x^2) = x^3 + 2 x^2 + 2 x + 1$$

$ n \quad \text{3-tuple}$
$ 3 \quad 2,\;2,\;1$
$ 4 \quad 5,\;3,\;1$
$ 5 \quad 9,\;4,\;1$

So after expanding out the lhs of $\text{(1)}$, all that is required is to perform four (accumulating) additions to find the answer:

The group $S_5$ has $9$ permutations with (exactly) two inversions.