§8. Перестановки.

Определение. Пусть A={a₁, a₂,…, a_n} – произвольное множество. Перестановкой множества A называется любой порядок расположения элементов этого множества.

Общее количество перестановок множества, состоящего из n элементов, обозначим P_n.

Теорема 1.1. P_n=n!=1·2·3·…·n (n! читается так: «эн факториал»).

Доказательство. По индукции. Пусть множество A состоит из одного элемента: A={a}. Очевидно, что существует только одна перестановка этого множества равенство P₁=1! верно.

Пусть теперь мы знаем, чтоP_n1=(n1)!, а множество A состоит из n элементов. Для того, чтобы создать перестановку, необходимо сначала выбрать тот элемент, который будет первым. Сделать это можно n различными способами. После этого у нас остаётся n1 элемент, и расположить их сзади первого элемента можно (n1)! способами согласно предположению индукции. Таким образом, общее количество способов расположения равно n·(n1)!= n!.

Каждой перестановке (a_i1, a_i2,…, a_in ) элементов множества A={a₁, a₂,…, a_n} однозначно соответствует перестановка (i₁, i₂,…, i_n) их номеров. Поэтому в дальнейшем будем говорить только про перестановки множества {1, 2,…, n} натуральных чисел.

Определение. Пусть (p₁, p₂,…, p_n) – произвольная перестановка. Говорим, что пара (p_i, p_j) образует инверсию, если i<j, но p_i>p_j (то есть бóльшее число стоит раньше).

Общее количество инверсий в перестановке (p₁, p₂,…, p_n) обозначим I(p₁, p₂,…, p_n). Если это число чётно (нечётно), то перестановка называется чётной (нечётной).

Пример. I(4, 2, 1, 5, 3)=5, т.к. в данной перестановке мы имеем следующие инверсии: (4, 2), (4, 1), (4, 3), (2, 1), (5, 3).

Предложение 3. Если в перестановке поменять местами два числа, то её чётность изменится.

Доказательство. Предположим сначала, что меняются местами два соседних числа p_i и p_i+1. Если p_i<p_i+1, Тогда у нас сохранятся все инверсии, в которых участвует только одно из этих чисел. Если p_i<p_i+1, то у нас появится одна новая инверсия (p_i+1, p_i), а если p_i>p_i+1, то у нас исчезнет одна инверсия (p_i, p_i+1). В любом случае общее количество инверсий изменится на 1, а значит, чётность перестановки изменится.

Предположим теперь, что меняются местами произвольные числа p_i и p_i+к. Между ними находится k1 чисел

p_i+1,…, p_i+к1. (1.10)

Мы сначала будем перемещатьp_i назад поочерёдно меняя его с каждым из чисел (1.10), пока оно не окажется перед p_i+к. Теперь p_i и p_i+к стали соседними. Мы меняем их местами, и затем, перемещаем p_i+к вперёд, меняя поочерёдно с каждым из элементов (1.10) в обратном порядке. В итоге мы поменяем p_i и p_i+к местами и совершим нечётное количество 2(k1) +1 перестановок соседних элементов. Каждая из таких перестановок меняла чётность. В итоге чётность нашей перестановки изменится.