
4. Let $\sigma=\left(a_{1}, a_{2}, a_{3}, \ldots, a_{n}\right)$ be a permutation of $(1,2,3, \ldots, n)$. A pair $\left(a_{i}, a_{j}\right)$ is said to correspond to an inversion of $\sigma$, if $ia_{j}$. (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)$.) How many permutations of $(1,2,3, \ldots n)$, $(n \geq 3)$, have exactly two inversions?


Solution: In a permutation of $(1,2,3, \ldots, n)$, two inversions can occur in only one of the following two ways:

(A) Two disjoint consecutive pairs are interchanged:

$$
\begin{aligned}
& (1,2,3, j-1, j, j+1, j+2 \ldots k-1, k, k+1, k+2, \ldots, n) \\
& \quad \longrightarrow(1,2, \ldots j-1, j+1, j, j+2, \ldots, k-1, k+1, k, k+2, \ldots, n)
\end{aligned}
$$

(B) Each block of three consecutive integers can be permuted in any of the following 2 ways;

$$
\begin{aligned}
& (1,2,3, \ldots k, k+1, k+2, \ldots, n) \longrightarrow(1,2, \ldots, k+2, k, k+1, \ldots, n) \\
& (1,2,3, \ldots k, k+1, k+2, \ldots, n) \longrightarrow(1,2, \ldots, k+1, k+2, k, \ldots, n)
\end{aligned}
$$

Consider case (A). For $j=1$, there are $n-3$ possible values of $k$; for $j=2$, there are $n-4$ possibilities for $k$ and so on. Thus the number of permutations with two inversions of this type is

$$
1+2+\cdots+(n-3)=\frac{(n-3)(n-2)}{2}
$$

In case (B), we see that there are $n-2$ permutations of each type, since $k$ can take values from 1 to $n-2$. Hence we get $2(n-2)$ permutations of this type.

Finally, the number of permutations with two inversions is

$$
\frac{(n-3)(n-2)}{2}+2(n-2)=\frac{(n+1)(n-2)}{2}
$$
