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

Date: 2015-10-07; view: 427.

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

Решение

,

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

Рассмотрим множество 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} является нечетной, поскольку представляет собой последовательность трех транспозиций.

Примеры:

***

***