Перестановки и транспозиции

Определители

Решение

,

Следовательно,

Рассмотрим множество S натуральных чисел от 1 до n, расположенных в порядке возрастания (в естественном порядке): S={1,2,3,...,n}

Под перестановкой множества S понимается множество этих же чисел, упорядоченное некоторым другим образом: {1,2,3,...,n}Þ{i₁,i₂,i₃,...,i_n}

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

Пример перестановки: {1,2,3,4} {2,4,1,3} {4,2,1,3}

Пример транспозиции: {1,3,2,4}

Любую перестановку множества S можно осуществить посредством нескольких транспозиций. Например, перестановка {2,4,1,3} является результатом трех транспозиций множества S: {1,2,3,4}Þ {3,2,1,4}Þ {4,2,1,3}Þ {2,4,1,3}.

Говорят, что перестановка множества S содержит инверсию элементов i_j и i_k, если нарушен их естественный порядок расположения, т.е. больший элемент расположен левее меньшего: i_j > i_k (j < k). Например, перестановка {2, 4, 1, 3} содержит три инверсии элементов: 2 и 1, 4 и 1, 4 и 3. Число инверсий определяет четность перестановки. Перестановка называется четной, если она содержит четное число инверсий элементов. Нечетная перестановка содержит нечетное число инверсий.

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

Пример: Перестановка {2, 4, 1, 3} является нечетной, поскольку содержит 3 инверсии элементов.
Можно также сказать, что перестановка {2, 4, 1, 3} является нечетной, поскольку представляет собой последовательность трех транспозиций.

Примеры:

1. Множество S = {1, 2, 3} содержит три элемента, и поэтому число различных перестановок этого множества равно 3! = 6:

{1, 2, 3}, {1, 3, 2}, {2, 3, 1}, {2, 1, 3}, {3, 1, 2} {3, 2, 1}.

***

1. Показать, что перестановка P = {2, 3, 1} является четной. Решение. Элементы 2 и 1 образуют инверсию, поскольку число 2 расположено слева от меньшего числа 1. Элементы 3 и 1 образуют инверсию, поскольку число 3 расположено слева от меньшего числа 1.

Таким образом, перестановка P содержит четное число инверсий. Другое решение. Перестановка P является четной, поскольку представляет собой результат четного числа последовательных транспозиций элементов множества S = {1, 2, 3}: {1, 2, 3} ⇒ {1, 3, 2} ⇒ {2, 3, 1}.

***

1. Показать, что перестановка Q = {3, 1, 2} является четной. Решение. Достаточно показать, что перестановка Q содержит четное число инверсий. Элементы 3 и 1 образуют инверсию, поскольку число 3 расположено слева от меньшего числа 1. Элементы 3 и 2 образуют инверсию, поскольку число 3 расположено слева от меньшего числа 2. Элементы 1 и 2 не образуют инверсию.

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

Дата добавления: 2014-12-16