# Find number of permutations with 2 inversions

Suppose $$\sigma=(a_1,a_2,a_3...,a_n)$$ be a permutation of $$(1,2,3,...n)$$. A pair $$(a_i,a_j)$$ is said to correspond to an inversion of $$\sigma$$, if $$i but $$a_i > a_j$$. How many permutations of $$(1,2,3...n)$$, $$(n\geq 3)$$, have exactly $$2$$ inversions?

Example: In the permutation $$(2,4,5,3,1)$$, there are 6 inversions corresponding to the pairs $$(2,1),(4,3), (4,1), (5,3), (5,1), (3,1)$$.

Can anyone give a recursive proof for this one? I tried to get one, but I dont get a proper solution..

• What is the answer for $n=3?$ For $n=4?$ Commented Jan 14, 2019 at 16:54
• Does it have to be recursive? I think a direct proof is easier Commented Jan 14, 2019 at 17:06
• I thought recursive proofs were easier, but if there is an easier proof than a recursive one, I am still OK with it. Commented Jan 14, 2019 at 17:15
• They can be, but not always. Have you done the $n=3$ and $n=4$ cases like saulspatz suggested? Commented Jan 14, 2019 at 17:20
• Nope,( as I said earlier, I was trying to get a recursive one without knowing there were other easier proofs, so I left that computation part halfway...) I am doing it. Commented Jan 14, 2019 at 17:26

Consider the following method of building a permutation. For each number in $$\{1,2,\dots,n\}$$ in increasing order, insert it anywhere in the line of the previously made numbers. The $$i^{th}$$ number can be inserted in $$i$$ places, and the number of inversions that insertion will add is anywhere between $$0$$ and $$i-1$$. For example, there is only one place to put $$1$$, effectively creating the list. There are $$2$$ places to put $$2$$, either before or after the $$1$$.
How many ways are there to end up with two inversions? There are two ways this can happen; either there were two steps which each created one inversion (and every other step made zero), or there was only one step which created two inversions. In the former case, there are $$\binom{n-1}2$$ ways to choose the two steps which created the inversions (as the first step, where $$1$$ is inserted into an empty list, cannot create any inversions), and there is are $$n-2$$ ways to choose a step where two inversions are created (as this cannot happen on the first or second steps). Therefore, the total number of ways is $$\binom{n-1}2+n-2 = \frac{(n+1)(n-2)}2$$
• I was trying to use the approach you mentioned to come up with a formula for the number of permutations with exactly 3 inversions. I have $$\binom{n-1}{3}+(n-2)(n-1)+(n-3)$$ which is over counting. I feel like it is the second term. Is there an easy way to come up with a formula for the number of permutations with exactly 3 inversions as well?
• Yes, you are overcounting with the second term. Everything else in your expression is correct. $\tag*{}$There are $(n-1)$ ways to choose the insertion which creates one inversion. However, the number of options for the insertion giving two inversion depends on whether or not the first choice was $1$. If you first choose $1$, there are $(n-1)$ options for the second choice, and if you first choose any other number, there are $(n-2)$ options for the second number. Can you put that altogether? Commented Apr 5, 2023 at 4:54
• Okay, so if the first choice is 1 then we have $n-1$ options for the second choice. If the first choice is not 1 then we have $n-1$ options for the first number with $n-2$ options for the second number. So we have $(n-1)+(n-1)(n-2)$?