Перестановки
Пусть $a=\{ 1, 2, ..., n-1, n\}$ последовательность натуральных чисел, а $b=\{ j_{1}, j_2, ..., j_n\}$ — последовательность тех же чисел, но взятых в другом (том же) порядке.
Так как среди чисел $j_{1}, j_2, ..., j_n$ нет одинаковых, то в качестве первого числа $j_{1}$ можно взять любое из чисел от 1 до $n$. Поэтому имеем ровно $n$ вариантов выбора. В качестве второго числа $j_2$ можно взять любое из $n-1$ оставшихся, то есть имеем $n-1$ вариантов выбора. Таким образом, получаем $n(n-1)$ различных способов выбора первых двух элементов. Продолжая аналогичные рассуждения, убеждаемся, что число различных перестановок из $n$ чисел равно $n!$.
Пусть дана некоторая перестановка $\{j_{1}, ..., j_{k}, ..., j_{s}, ..., j_n\}$. Допустим, что в результате транспозиции $(k, s)$ элементы $j_{k}$ и $j_{s}$ поменялись местами. Число элементов между ними равно $s-k-1$. Меняем местами $j_{k+1}$ и $j_{s}$, затем $j_{k+2}$ и $j_{s}$ и так далее После $s-k-1$ транспозиций получаем перестановку $\{ j_{1}, ..., j_{k-1}, j_{k+1}, ..., j_{s}, j_{k}, j_{s+1}, ..., j_n \} $. Меняем теперь местами $j_{k}$ и $j_{s}$, потом $j_{k}$ и $j_{s-1}$ и так далее В результате $s-k$ транспозиций приходим к исходной перестановке. Всего совершено нечетное число $2(s-k)-1$ транспозиций соседних элементов.
Допустим, что в перестановке $a=\{ j_{1}, ..., j_{k}, j_{k+1}, ..., j_n \} $ сделана транспозиция $(k, k+1)$, получаем $b=\{ j_{1}, ..., j_{k+1}, j_{k}, ..., j_n \}$. Понятно, что число инверсий в перестановках, не содержащих элементы $j_{k}$ и $j_{k+1}$, совпадают. Больше того, если из перестановок $a$ и $b$ исключить один из этих элементов, то число инверсий в оставшихся перестановках также будут совпадать, поскольку каждый из них не меняет своего положения относительно других элементов. Тогда становится очевидным, что если $j_{k} >j_{k+1} $, то $inv \{a\} = inv \{b\} + 1$, тогда как в случае $j_{k} <j_{k+1} $ имеем $inv \{b\} = inv \{a\} + 1$.
Допустим, что число четных перестановок равно $p$, а число нечетных $q$. Если во всех четных перестановках сделать транспозицию $(1, 2)$, то получим $p$ нечетных перестановок, следовательно, $p\le q$. С другой стороны, если во всех нечетных перестановках также произвести транспозицию $(1, 2)$, то получаем $q$ четных. Но по условию всего их было $p$, поэтому $q\le p$. Отсюда следует, что $p=q$.
Доказательство проведем методом математической индукции. Если $n=2$, то утверждение очевидно. Пусть теорема доказана для случая, когда в перестановке $n-1$ элементов. Докажем утверждение, когда элементов $n$.
Рассмотрим две произвольные перестановки $a=\{\alpha_{1}, \alpha_2, ..., \alpha_n\} $ и $b=\{\beta_{1}, \beta_2, ..., \beta_n\}$. Если $\alpha_{1} =\beta_{1}$, то поскольку перестановки $\{ \alpha_2, \alpha_3, ..., \alpha_n \} $ и $\{ \beta_2, \beta_3, ..., \beta_n \} $ содержат $n-1$ элементов, то в соответствии с индукционным предположением посредством нескольких транспозиций одна из них приводится к другой.
Пусть $\alpha_{1} \ne \beta_{1}$, но, понятно, что существует такой элемент $\beta_{j}$, что $\alpha_{1} =\beta_{j} $. Если сделать транспозицию $(1, j)$ в $b$, то получаем перестановку, в которой первый элемент совпадает с первым элементом $a$. Таким образом, приходим к уже рассмотренному случаю.