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

Def. Упорядоченное множество чисел , среди которых нет равных и каждое из которых принимает одно из значений 1, 2, 3, …, n, называют перестановкой.

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

Элемент может быть размещен в перестановке n способами, – n-1 способами и т.д., – 2 способами, – единственным способом. Согласно правилу умножения комбинаторики все n элементов можно расположить способами.

Def. Говорят, что элементы i и j в перестановке образуют инверсию, если , но элемент i расположен левее.

Чтобы сосчитать число инверсий, образуемых элементами перестановки, поступают следующим образом. Сначала надо сосчитать сколько элементов стоит в перестановке перед 1 (именно они будут образовывать инверсию с 1). После этого вычеркиваем 1 и считаем количество чисел, стоящих перед 2 (это и будет количество инверсий, образуемых 2 с оставшимися элементами). Затем вычеркиваем 2 и т.д.

Общее число инверсий в перестановке обозначается .

N. .

Def. Перестановка называется четной (нечетной), если ее элементы образуют четное (нечетное) число инверсий.

Def. Транспозицией называется операция перемены мест любых двух элементов.

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

1) Рассмотрим случай, когда меняются соседние элементы. Пусть перестановка до транспозиции имела вид: . Поменяем местами и . Очевидно, что элементы и образуют такое же количество инверсий, что и до транспозиции. Если элементы и не образовывали инверсии, то и будут образовывать инверсию и наоборот. Таким образом, общее число инверсий в результате такой транспозиции либо уменьшится на одну, либо увеличится на одну. Значит, четность перестановки изменится на противоположную.

2) Рассмотрим случай, когда меняются не соседние элементы. Пусть пере­становка до транспозиции имела вид:

.

Поменяем местами элемент последовательно с элементами . При этом имеем k транспозиций соседних элементов. Затем поменяем местами и (еще 1 транспозиция). И, наконец, поменяем местами элемент последовательно с элементами (k инверсий). Таким образом поменялись местами элементы и поменялись местами в результате транспозиции. Т.к. каждая транспозиция соседних элементов по доказанному меняет четность перестановки, то четность исходной перестановки изменится.

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

Пусть p – число четных перестановок и q – число нечетных перестановок. В каждой четной перестановке выполним одну транспозицию. В силу Th.2.2 получим р нечетных перестановок. Поскольку общее число нечетных перестановок равно q, то очевидно . Аналогично, выполнив одну транспозицию в каждой нечетной перестановки, то получим, что . Следовательно, .

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