Приложение 2. Некоторые сведения из теории множеств

Некоторые сведения из теории множеств.
Комбинаторика.
Перестановки и подстановки

Рассмотрим упорядоченное множество из n элементов. Пусть это будет множество натуральных чисел

1, 2, 3, …, n.

Установленный в конечном множестве порядок называют перестановкой его элементов. Число перестановок конечного множества элементов зависит только от числа элементов. Для множества из n элементов число перестановок обозначают Р_n

Р_n = 1 × 2 × 3 × …× (n – 1) n = n! (читается n-факториал)

Рассмотрим некоторую перестановку множества из n элементов

(… i … j …).

Числа i и j называются инверсией, если i в перестановке стоит раньше, чем j, но i < j.

Если число инверсий в перестановке четное, то и перестановка называется четной, если нечетное число инверсий, то и перестановка называется нечетной.

Например, n = 5, тогда (1, 2, 3, 4, 5) – одна из возможных 5! перестановок этого множества. Очевидно, что в этой перестановке нуль инверсий.

Рассмотрим какую-нибудь другую перестановку множества из пяти элементов. Например,

(3, 5, 2, 1, 4)

Перечислим пары чисел, которые составляют инверсии

3 и 2, 3 и 1, 5 и 2, 5 и 1, 5 и 4, 2 и 1.

Таким образом, в этой перестановке число инверсий – 6. Перестановка – четная.

Очевидно, что максимальное число инверсий будет соответствовать перестановке, где все элементы взяты в обратном порядке:

(5, 4, 3, 2, 1)

Для перестановки множества из 5 элементов максимальное число инверсий 10.

Часто возникает вопрос: чему равно максимальное число инверсий в перестановке множества из n элементов?

Очевидно, что минимальное число инверсий 0 соответствует прямой перестановке (1, 2, 3, …, n), а максимальное число соответствует обратной перестановке (n, n – 1, n – 2, …, 3, 2, 1).

С элементом n составляют инверсии остальные (n – 1)-элементы, с
(n – 1) – остальные (n – 2)-элементы, стоящие за ним справа, и т.д.

Тогда

[max число инверсий] = (n – 1) + (n + 2) + … + 2 + 1 = S_n–1,

где S_n–1 – сумма (n – 1)-числа натурального ряда, которую можно вычислить как сумму убывающей арифметической прогрессии, начинающейся с (n – 1) с разностью прогрессии (- 1):

Таким образом, число инверсий изменяется от 0 до .

Количество четных и нечетных перестановок очевидно одинаково.

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

a₁ a₂ … a_n

1 2 … n, где

(a₁ a₂ … a_n) – одна из (n!) перестановок множества.

Часто говорят, «a₁» переходит в «1», «a₂» - в «2», …, «a_n» - в n.

Очевидно, что в подстановке из n элементов можно перебрать n! различных подстановок.

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

Поиск по сайту: