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

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!

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$$

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}$$

• Could you tell me which ones I am missing. Also this question is from an exam so is it just expected to be trial + error to determine them all? Commented May 14, 2017 at 20:11
• @BenB I have updated my answer with the pemutations that have exactly $2$ inversions. I think a more systematic approach is required than trial and error. As you have found out, you will need a method that doesn't miss any. Such a method can be found but I would use understanding of the $q$-analogue to derive it. Commented May 14, 2017 at 21:59

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.