Перестановки конечного множества элементов.

Лекция 5

Раздел 4. Определители.

Перестановки конечного множества элементов.

Рассмотрим конечное множество состоящее из п элементов .

Определение 1.Всякое расположение чисел множества S в некотором определенном порядке называется перестановкой из п чисел и обозначается .Через обозначим число всех перестановок множества S.

Пример. Для множества выпишем множество всех перестановок:

.

Число всех перестановок этого множества .

Теорема. Число перестановок множества равно , т.е. .

Доказательство. Общий вид перестановки множества S в виде:

, (*)

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

В качестве первого элемента можно взять любое из чисел . Это даст п различных перестановок. На место элемента можно взять лишь одно из оставшихся чисел. Следовательно, число различных способов выбрать и равно произведению . Продолжая дальше, на место можно выбрать одно из оставшихся чисел и т.д. Обобщая, придем к выводу, что число перестановок множества будет равно .

Пример. Покажем, что число перестановок множества равно .

1 2 3 4

2 3 4 1 3 4 1 2 4 1 2 3

3 4 2 4 2 3 3 4 4 1 1 3 2 4 1 4 1 2 2 3 1 3 1 2

4 3 4 2 3 2 4 3 1 4 3 1 4 2 4 1 2 1 3 2 3 1 2 1

Определение 2. Если в перестановке поменять местами какие-либо два символа, а все остальные оставить на месте, то получим новую перестановку. Эта операция называется транспозицией.

Утверждение. От любой перестановки множества S можно перейти к любой другой перестановке этого множества при помощи нескольких транспозиций.

Пример. Пусть . Покажем, как при помощи нескольких транспозиций из перестановки можно получить перестановку :

Определение 3. Говорят, что в перестановке пара чисел и образуют инверсию, если при , т.е. число с большим значением стоит раньше.

Пример. Сколько инверсий в перестановке ? Перестановка имеет инверсии: (32), (31), (85), (82), (84),(86), (87), (81), (52), (54), (51), (21), (41), (61), (71). Всего 15 инверсий.

Если число инверсий в перестановке обозначим , то для предыдущего примера можно записать .

Определение 4. Перестановка называется четной, если ее символы составляют четное число инверсий, и нечетной – в противном случае.

Утверждение.Всякая транспозиция меняет четность перестановки.

Пример. Рассмотрим перестановку из 5 элементов . У этой перестановки три инверсии (32), (52), (54), т.е. , поэтому перестановка нечетная.

Поменяем местами второй и пятый элементы , получим новую перестановку . У этой перестановки четыре инверсии (42), (43), (52), (53), т.е. , поэтому перестановка четная.