Перестановки та підстановки
ПЕРЕСТАНОВКИ І ПІДСТАНОВКИ §1. Перестановки із n чисел
Нехай М - деяка кінцева множина з n елементів.
Визначення. Будь-яке розташування елементів цієї множини у певному порядку називається перестановкою з n символів.
Наприклад, якщо М = < ◊ , • , х >, то õ , • , ◊ – перестановка із трьох символів.
Елементи множини М можна занумерувати числами 1,2,3,...,n; тому замість перестановок елементів із М можна розглядати лише перестановки чисел (1).
Методом математичної індукції легко доводиться Теорема 1. Число різних перестановок із n чисел дорівнює n! Доказ цієї теореми наведено у [1].
Визначення 1. Якщо в деякій перестановці з n чисел число i коштує раніше, ніж j, але i>j, тобто більше число коштує раніше меншого, то кажуть, що пара i,j становить інверсію.
Наприклад, у перестановці 3,1,4,2 (2) пари 3,1; 4,2 та 3,2 складають інверсії.
Визначення 2. Перестановка називається парною, якщо загальна кількість інверсій у ній парна; в іншому випадку перестановка непарна.
Перестановка (2) непарна, т.к. у ній лише три інверсії.
Визначення 3. Нехай дана деяка перестановка
…, i. j. (3). Перетворення, у якому числа i і j змінюються місцями, інші залишаються у своїх місцях, називається транспозицією.
Після транспозиції чисел i та j у перестановці (3) отримаємо перестановку …, j. i. (4), де всі елементи, крім i та j, залишилися на своїх місцях.
Теорема 2. Від будь-якої перестановки із n чисел можна перейти до будь-якої іншої перестановки з цих чисел за допомогою кількох транспозицій.
Доведення . Нехай потрібно перейти від перестановки i 1, i 2,. i n (5) до перестановки j 1 ,j 2 , . j n (6). У перестановці (5) робимо транспозицію чисел i 1 і j 1 ; отримаємо j 1 , i 2 , . i 1 , . i n (7). У перестановці (7) робимо транспозицію чисел i 2 і j 2 : j 1 , j 2 , i 3 . i n і т.д. Через кінцеве число кроків із перестановки (5) отримаємо (6). Теорему доведено.
Теорема 3. Будь-яка транспозиція змінює парність перестановки. Доказ цієї теореми наведено у [1].
Теорема 4. При n≥2 число парних та непарних перестановок з n чисел однаково
Доведення. Введемо позначення: Ч – безліч всіх парних перестановок із n чисел, Н – безліч всіх непарних перестановок із тих самих чисел. Т.к. n≥2, то серед чисел < 1,2. n >існують два
різних числа i, j. У всіх перестановках із n чисел проведемо транспозицію чисел i та j. Тоді безліч
Ч перейде до множини Н 1 і це відображення Ч → Н 1 – бієкція. За теоремою 3 Н 1 Н. Значить, число елементів множини Ч і число елементів множини Н пов'язані нерівністю: Ч ≤ Н (8). Аналогічно з огляду на те, що непарні перестановки при транспозиції чисел i і j перейдуть у парні, можна показати, що Н≤Ч (9). З нерівностей (8) і (9) випливає, що Н=Ч, тоді з теореми 1 отримуємо, що число парних і
непарних перестановок з n чисел дорівнює n 2! . Теорему доведено.
§2. Підстановки ступеня
Визначення 1. Нехай М – кінцева множина з n елементів. Будь-яке бієктивне перетворення
множини М називається підстановкою ступеня.
Зручно елементи множини М занумерувати
підстановки елементів цієї множини. Але запис у вигляді
де i k(1), k < 1. n>і все
підстановку записують так:
f (k) = i, k 1, n.
У нижньому рядку
(10) і розуміють, що
підстановки f стоїть деякаперестановка із n чисел. Підстановка (10) називається підстановкою
Зауважимо, що з визначення підстановки слід, що її стовпці можна довільним чином міняти місцями, т.к. отримаємо те саме перетворення (тобто. ту саму підстановку).
Визначення 2. Підстановка називається парною, якщо обидві її рядки (перестановки) мають однакові парності, тобто. або обидві парні, або обидві парні. В іншому випадку підстановка називається
Доведемо, що визначення коректно, тобто. не залежить від форми запису підстановки.
Нехай задана підстановка f. Дві її різні форми запису відрізняються лише порядком розташування стовпців. В силу теореми 2 від одного розташування стовпців можна перейти до іншого розташування (перестановки) цих стовпців за допомогою декількох транспозицій стовпців. У силу теореми 3 при кожній транспозиції стовпців парності верхньої та нижньої перестановок змінюється, проте зберігається збіг (несупад) парностей рядків. За визначенням парність підстановки у своїй не змінюється. Цим доведено, що при будь-якій перестановці стовпців підстановки f її парність та сама (тобто парність підстановки f не залежить від форми її запису).
1 . Неважко бачити, що парність підстановки можна визначити інакше: підстановка називається парною, якщо загальна кількість інверсій верхньої та нижньої рядків парно, інакше підстановка непарна.
Очевидно, будь-яку підстановку можна записати у стандартному вигляді (10). При такому записі парність підстановки визначається лише парністю її нижнього рядка.
Тепер із теореми 4 отримуємо
Твердження. При n≥2 число парних та непарних підстановок ступеня однаково і дорівнює n 2 ! .
Підстановки - це перетворення кінцевої множини, тому їх можна перемножувати поправил множення відображень.