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

Пусть последовательность натуральных чисел, а — последовательность тех же чисел, но взятых в другом (том же) порядке.

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

Лемма 2.3.1.Число различных перестановок последовательности a равно n!.

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

Определение 2.3.2. Будем говорить, что пара элементов , , перестановки b образуют инверсию, если . Число всех пар перестановки b, образующих инверсию, называется числом инверсий в b и обозначается .

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

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

Теорема 2.3.1.Если в некоторой перестановке сделана транспозиция, то она равна произведению нечетного числа транспозиций соседних элементов.

Доказательство.Пусть дана некоторая перестановка . Допустим, что в результате транспозиции (k, s) элементы и поменялись местами. Число элементов между ними равно . Меняем местами и , затем и и т. д. После транспозиций получаем перестановку . Меняем теперь местами и , потом и и т. д. В результате транспозиций приходим к исходной перестановке. Всего совершено нечетное число транспозиций соседних элементов.

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

Доказательство.Допустим, что в перестановке сделана транспозиция , получаем Понятно, что число инверсий в перестановках, не содержащих элементы и , совпадают. Больше того, если из перестановок и исключить один из этих элементов, то число инверсий в оставшихся перестановках также будут совпадать, поскольку каждый из них не меняет своего положения относительно других элементов. Тогда становится очевидным, что если , то , тогда как в случае имеем .

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

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

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

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

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

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

Рассмотрим две произвольные перестановки и . Если , то поскольку перестановки и содержат элементов, то в соответствии с индукционным предположением посредством нескольких транспозиций одна из них приводится к другой.

Пусть , но, понятно, что существует такой элемент , что . Если сделать транспозицию в , то получаем перестановку, в которой первый элемент совпадает с первым элементом a. Таким образом, приходим к уже рассмотренному случаю.