Розділ 4. Визначники.
Перестановки кінцевого безлічі елементів.
Розглянемо кінцеве безліч складається з п елементів.
Визначення 1. Будь-яке розташування чисел безлічі S в деякому певному порядку називається перестановкою з п чисел і позначається .Через позначимо число всіх перестановок безлічі S.
Приклад. Для безлічі випишемо безліч всіх перестановок:
Число всіх перестановок цього безлічі.
Теорема. Число перестановок безлічі одно. тобто .
Доведення. Загальний вигляд перестановки множини S у вигляді:
де кожне є одне з чисел. причому, жодне з цих чисел не зустрічається двічі в вираженні (*).
В якості першого елемента можна взяти будь-яке з чисел. Це дасть п різних перестановок. На місце елемента можна взяти лише одне з решти чисел. Отже, число різних способів вибрати і дорівнює добутку. Продовжуючи далі, на місце можна вибрати одне з решти чисел і т.д. Узагальнюючи, прийдемо до висновку, що число перестановок безлічі дорівнюватиме.
Приклад. Покажемо, що число перестановок безлічі одно.
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), тобто . тому перестановка парна.