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<j$ 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..
Best Answer
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 $$