Перестановки

Пусть $a=\{ 1, 2, ..., n-1, n\}$ последовательность натуральных чисел, а $b=\{ j_{1}, j_2, ..., j_n\}$ — последовательность тех же чисел, но взятых в другом (том же) порядке.

Определение:

Последовательность $b$ называется перестановкой последовательности $a$.

Лемма:

Число различных перестановок последовательности a равно $n!=n(n-1)(n-2)\cdots 2\cdot 1$.

Доказательство:

Так как среди чисел $j_{1}, j_2, ..., j_n$ нет одинаковых, то в качестве первого числа $j_{1}$ можно взять любое из чисел от 1 до $n$. Поэтому имеем ровно $n$ вариантов выбора. В качестве второго числа $j_2$ можно взять любое из $n-1$ оставшихся, то есть имеем $n-1$ вариантов выбора. Таким образом, получаем $n(n-1)$ различных способов выбора первых двух элементов. Продолжая аналогичные рассуждения, убеждаемся, что число различных перестановок из $n$ чисел равно $n!$.

[math]\displaystyle{ \blacksquare }[/math]

Определение:

Будем говорить, что пара элементов $(j_{k}, j_{m})$, $k<m$, перестановки $b$ образует инверсию, если $j_{k} > j_{m}$. Число всех пар перестановки $b$, образующих инверсию, называется числом инверсий в $b$ и обозначается $inv\{b\}$.

Определение:

Перестановка, содержащая четное число инверсий, называется четной, а нечетное число — нечетной.

Определение:

Если в некоторой перестановке $j$-й и $k$-й элементы поменять местами, оставив без изменения положение остальных $n-2$ элементов, то такая операция называется транспозицией и обозначается $(j, k)$.

Теорема:

Пусть в некоторой перестановке сделана транспозиция. Полученная перестановка приводится к исходной в результате нечетного числа транспозиций соседних элементов.

Доказательство:

Пусть дана некоторая перестановка $\{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$ транспозиций соседних элементов.

[math]\displaystyle{ \blacksquare }[/math]

Теорема:

При транспозиции соседних элементов число инверсий в перестановке меняется на единицу.

Доказательство:

Допустим, что в перестановке $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$.

[math]\displaystyle{ \blacksquare }[/math]

Следствие:

При транспозиции соседних элементов четная перестановка становится нечетной, а нечетная — четной.

Следствие:

Любая транспозиция меняет четность перестановки на противоположную.

Теорема:

Число четных перестановок всегда совпадает с числом нечетных.

Доказательство:

Допустим, что число четных перестановок равно $p$, а число нечетных $q$. Если во всех четных перестановках сделать транспозицию $(1, 2)$, то получим $p$ нечетных перестановок, следовательно, $p\le q$. С другой стороны, если во всех нечетных перестановках также произвести транспозицию $(1, 2)$, то получаем $q$ четных. Но по условию всего их было $p$, поэтому $q\le p$. Отсюда следует, что $p=q$.

[math]\displaystyle{ \blacksquare }[/math]

Теорема:

Любая перестановка может быть получена из любой другой посредством нескольких транспозиций.

Доказательство:

Доказательство проведем методом математической индукции. Если $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$. Таким образом, приходим к уже рассмотренному случаю.

[math]\displaystyle{ \blacksquare }[/math]