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

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

Определение. Подмножество k элементов из множества n элементов называется соединением из n элементов по k.

Определение. Соединение из n элементов по n называется перестановкой.

Количество перестановок вычисляется по формуле: Р = n!, где n! = 1 , т.е. произведение последовательных натуральных чисел от 1 до n. Например, 4! = 1 = 24. Считается, что 0! = 1.

Определение. Соединение из n элементов по k называется сочетанием, если порядок следования элементов в нем не учитывается.

Количество сочетаний вычисляется по формуле:

С = .

Например,

С = = = 10.

Определение. Соединение из n элементов по k называется размещением, если порядок следования элементов в нем учитывается.

Количество размещений вычисляется по формуле:

А = .

Например:

А = = = 60.

Доказательство приведенных выше трех формул можно осуществить методом полной математической индукции. Докажем формулу количества перестановок. Для n = 1, 2 формула очевидно верна. Допустим, что формула верна для m 2. Надо доказать справедливость формулы для n = m +1. Перестановка (a a …a a ) содержит m + 1 элементов. Из первых m элементов можно согласно допущению сделать m! перестановок. Все перестановки из (m + 1) элементов можно получить из них, ставя а последовательно на первое, второе, третье и т. д. место. Всего перестановок из (m + 1) элементов получается m!(m +1) = (m +1)! штук. Что и требовалось доказать.

С этого момента будем считать, что элементами перестановок являются натуральные числа от 1 до n, при этом главной из них будем считать перестановку (1 2 3 4 … n). Говорят, что два числа в перестановке образуют инверсию (беспорядок), если меньшее из них стоит правее большего. Например, в перестановке (2 7 1 4 3 6 5) инверсию образуют восемь пар чисел:

(2 1), (7 1), (7 3), (4 3), (7 4), (6 5), (7,5), (7 6),

а в перестановке (2 7 1 3 4 6 5) инверсию образуют семь пар чисел:

(2 1), (7 1), (7 3), (7 4), (7 5), (6 5), (7 6).

Определение. Перестановка называется четной (нечетной), если число инверсий в ней четное (нечетное).

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

Перестановка (2 7 1 3 4 6 5) нечетная, она получена из четной перестановки (2 7 1 4 3 6 5) путем перемены местами чисел 3 и 4. На этом примере видим, что транспозиция меняет четность перестановки на нечетность, а нечетность на четность.

Теорема 1.1. Любая транспозиция переводит четную перестановку в нечетную, а нечетную – в четную.

Доказательство. Пусть P (с с ... с с … с с … с ) – произвольная перестановка. Рассмотрим случай, когда переставляемые числа стоят рядом, пусть это будут числа с , с . Пусть Е – количество инверсий в перестановке Р . При перестановке чисел с , с местами число Е увеличивается или уменьшается на 1, если с < с , или с > с . Следовательно, если Е было четным, то оно переходит в нечетное, а если Е было нечетным, то оно переходит в четное число. Теперь рассмотрим случай, когда переставляемые числа не стоят рядом, пусть это будут числа с , с . Перестановку P запишем в виде P (с с ... с с А с … с ), где А – перестановка (с c … c ), в которой m = (k - j – 1) элементов. Последовательно переставляя с с каждым элементом перестановки А, а затем последовательно переставляя с с каждым элементом перестановки А, мы получим перестановку P (с с ... с с с А с … с ), в которой числа с и с стоят рядом. Переставляя местами с и с , получим перестановку P (с с ... с с с А с … с ), которая отличается от перестановки P (с с ... с с … с с … с ) тем, что числа с и с поменялись местами. Всего для получения перестановки P из P понадобилось осуществить (2 m +1) перемен местами рядом стоящих чисел. Так как (2 m +1) – нечетное число, то если P - четная перестановка, то P - нечетная перестановка, если же P - нечетная перестановка, то P - четная перестановка. Теорема доказана.

Следствие. Число четных перестановок из n элементов (n>1) равно числу нечетных, т. e. n!/2.

Дата добавления: 2015-07-26