Перестановки і підстановки

Обчислення визначників 4-го і більш високих порядків не може бути представлено досить простий «геометричній схемою», як це зроблено для визначників 2-го і 3-го порядків.

Для визначення і вивчення визначників n-го порядку використовуються поняття, що відносяться до кінцевих множин деяких елементів.

Розглянемо безліч М цілих чисел: 1, 2, .... n. Елементи безлічі М можна розташувати різними способами.

Визначення. будь-яке розташування чисел 1, 2, ..., n в деякому порядку називається пе-рестановкой з n чисел. Загальний вигляд запису перестановки з n елементів:

де кожне is є одне з чисел 1, 2, .... n, причому жодне з цих чисел не зустрічається двічі і не пропущено.

Як i1 можна вибрати будь-який з чисел 1, 2, .... n. Це дає n різних можливостей. Якщо i1 вже вибрано, то в якості i2 можна вибрати лише одне з решти (n -1) чисел, тобто різних способів вибрати числа (символи) i1 і i2 дорівнює добутку n # 8729; (N -1) і т.д. Число перестановок з n символів дорівнює добутку:

Якщо в деякій перестановці поміняємо місцями будь-які два символу (не обов'язково стоять поруч), а всі інші залишимо на місці, то отримаємо нову перестановку. Таке перетворення перестановки називається транспозицією.

Теорема 1. Всі перестановки з n символів можна розташувати в такому порядку, що кожна наступна перестановка виходить з попередньої однієї транспозицией, причому починати можна з будь-якої перестановки.

► При n = 2 твердження справедливо: 1, 2 → 2, 1;

Розглянемо всі перестановки з n елементів, у яких на першому місці стоїть символ i1. Таких перестановок і їх можна впорядкувати відповідно до вимог теореми для (n -1) символів. Нехай остання з таких перестановок (з урахуванням того, що символ i1 був весь час непереміщуваними) має вигляд:

В перестановці (43), що містить n символів, зробимо транспозицию символу i1 з будь-яким іншим (наприклад, з символом i2) і знову впорядкуємо всі перестановки з (n -1) символів при фіксованому на першому місці i2 і т.д. Так можна перебрати всі перестановки з n символів. ◄

Слідство. від будь-якої перестановки з n символів можна перейти до будь-якої іншої перестановці з тих же символів за допомогою декількох транспозицией.

Якщо в перестановці символ i1 варто раніше, ніж символ i2. але. то кажуть, символи i1 і i2 складають інверсію (порушення порядку), інакше зазначені символи складають порядок. Перестановка називається парною. якщо її символи складають парне число інверсій, і непарній - в іншому випадку.

Зауваження. 1) будь-яка транспозиція змінює парність перестановки.

2) сума порядків і інверсій постійна і дорівнює

# 9786; Приклад 31. Визначимо парність перестановки 1, 2, .... n.

Рішення. Задана перестановка парна, тому що в ній немає інверсій (порушень порядку).

Приклад 32. Визначте парність перестановки 4 5 1 3 6 2.

Рішення. Для підрахунку числа інверсій скористаємося таблицею 1, у якій вказані інверсії виділяються елементів з усіма подальшими (облік порушень порядку).

Приклад 33. Вкажіть число інверсій в перестановці: 1, 9, 6, 3, 2, 5, 4, 7, 8.

Приклад 34. В якій перестановці чисел 1, 2, 3, ..., 99 число інверсій найбільше і чому воно дорівнює?

Приклад 35. Скільки інверсій утворює число 99, що стоїть на 50 місці в перестановці 1, 2, ..., 99.

1. Перестановка - це матриця?

2. Що таке «транспозиція» двох елементів перестановки?

3. Що таке «інверсія» для двох виділених елементів перестановки?

4. Що таке «порядок» для двох виділених елементів перестановки?

5. Чому дорівнює сума числа інверсій і числа порядків в будь-який перестановці чисел 1, 2, .... 99.

Визначення. Запишемо одну перестановку під інший:. цей запис

називають підстановкою. розуміючи під цим відображення (відповідність) безлічі символів, що складається з перших n чисел: 1, 2, ..., n, на себе. ; . . ...,

Якщо врахувати, що підстановка як відображення безлічі чисел 1, 2, .... n не змінюється при транспозиції стовпців, виберемо для неї найпростіше вираження:

де # 945; i - число, в яке переходить число i.

У вираженні (44) підстановки порядку n розрізняються тільки перестановками в нижньому рядку записи, тобто підстановку однозначно визначає перестановка. записаний-ва в її нижньому рядку. Це означає, що всього підстановок порядку n стільки ж, скільки-ко і перестановок, тобто .

Визначимо поняття парності для підстановок:

А. Виходячи із загального визначення підстановки:

- підстановка парна. якщо парності верхньої і нижньої перестановок збігаються;

- підстановка непарна. якщо парності верхньої і нижньої перестановок протилежні.

Б. З огляду на приватну запис підстановки (44):

- підстановка парна. якщо її визначає парна перестановок;

- підстановка непарна. якщо її визначає непарна перестановка.

Крім підрахунку числа інверсій в перестановках для визначення парності підстановок застосовують також розкладання їх у цикли. Скористаємося цим прийомом (НЕ обгрунтовуючи його, приймемо на віру), розглянувши конкретний приклад.

# 9786; Приклад 36. Визначимо парність підстановки.

Рішення. Для визначення парності підстановки розкладемо її на витвір циклів:

де дужки після знака "=" відображають цикли: (1 → 6 → 3 → 1), (2 → 5 → 2), (4 → 4), (7 → 7), (8 → 8), (9 → 9 ) відображення символів 1,2, ..., 9 по визначенню підстановки (в циклах враховані також символи «залишаються на місці»). Маючи розкладання підстановки в цикли, визначимо число декремент. d = n - s, де n - порядок підстановки, s - число циклів в розкладанні підстановки. У розглянутому прикладі: d = 9 - 6 = 3 - непарне число → підстановка непарна.

Приклад 37. Для визначення парності підстановки розкладемо її на витвір циклів:

де дужки після знака "=" відображають цикли: (1 → 5 → 1), (2 → 8 → 6 → 4 → 2), (3 → 9 → 7 → 3) відображення символів 1,2, ..., 9 по визначенню підстановки. Обчислимо декремент для даної підстановки: d = 9 - 3 = 6 - парне число → підстановка парна.

Приклад 38. Вкажіть число інверсій в перестановці: 1, 9, 6, 3, 2, 5, 4, 7, 8.

Приклад 39. В якій перестановці чисел 1, 2, 3, ..., 99 число інверсій найбільше і чому воно дорівнює?

Приклад 40. Скільки інверсій утворює число 99, що стоїть на 50 місці в перестановці 1, 2, ..., 99.

6. Підстановка - це матриця?

7. Що таке «транспозиція» стовпців підстановки?

8. Що таке «інверсія» в підстановці?

9. Що таке «порядок» в підстановці?

10. Чому дорівнює сума числа інверсій і числа порядків в будь-який підстановці чисел 1, 2, .... 99.

Визначники n-го порядку

Нехай маємо квадратну матрицю n -го порядку:

елементами aij. якої можуть бути елементи будь-якого числового поля. Розглянемо всілякі твори по n елементів, розташованих в різних рядках і різних стовпчиках:

де - складають деяку перестановку з чисел 1, 2, .... n. Число таких творів одно числу перестановок, тобто .

Складемо підстановку з n символів. . (47)

Можна помітити, що в визначниках 2-го і 3-го порядків зі знаком "плюс" входять ті члени визначників, індекси яких складають парну підстановку, а зі знаком "мінус" - члени з непарної підстановкою індексів. Це властивість зберігають у визначенні визначників n-го порядку.

Визначення. визначником n -го порядку, відповідним матриці (45), називається алгебраїчна сума членів, складена таким чином:

- кожен член визначника (окреме доданок у зазначеній сумі) є твір n елементів визначника, взятих по одному з кожного стовпчика і кожного рядка матриці;

- член визначника береться зі знаком "плюс". якщо індекси складають парну підстановку, і зі знаком "мінус". якщо непарну:

Позначення визначника: (48)

Застосування визначення визначника n-го порядку для практичних обчислень було б важко. Досліджуємо його властивості, безпосередньо випливають з визначення.

З огляду на свойство1 визначників 3-го порядку, що встановлює рівноправність рядків і стовпців визначника, транспоніруем матрицю А і запишемо:

Нехай в визначнику виділений деякий член:

для визначення знака якого використовується підстановка n -го порядку:

в ній верхня перестановка відображає номери рядків визначника, в яких розміщені елементи матриці, що входять у вираз (50); а нижня - номери стовпців.

Після транспонування матриці А ті ж елементи будуть брати участь у вираженні члена визначника матриці:

причому для визначення знака, який матиме цей член в визначнику повинна використовуватися підстановка:

Очевидно, парності підстановок (51) і (53) збігаються (див. Визначення парності підстановки).

Нами доведено одне з найважливіших властивостей визначника n-го порядку (тепер уже для всіх n = 2, 3, ...):

Властивість 1. Визначник не змінюється при транспонировании матриці:.

Властивість 2. Якщо один з рядків визначника складається з нулів, то визначник дорівнює нулю (випливає з того, що якийсь із нулів цього рядка обов'язково увійде в вираз кожного з членів визначника).

Властивість 3. Якщо у визначнику переставлені два рядки (стовпці), то всі члени отриманого визначника ті ж, що і в початковому, але з протилежним знаком, тобто перестановка двох рядків визначника змінює його знак (випливає з представленої нижче схеми перетворення визначника і відповідних підстановок: їх парності помінялися!):

Властивість 4 Визначник, який має дві однакові рядки, дорівнює нулю (при перестановці цих рядків з властивості 3 випливає, що d = -d, тобто d = 0).

Властивість 5 Якщо всі елементи i -го рядка визначника помножити на довільне число k. то визначник множиться на число k (випливає з виразу (48) записи загального члена визначника: кожен член визначника містить рівно один елемент з i -го рядка, тому кожен із них набуває множник k. тобто сам визначник множиться на k.

Властивість 6 Визначник, у якому дві пропорційні рядки, дорівнює нулю (випливає з властивостей 5 і 4).

Властивість 7 Якщо всі елементи i -го рядка визначника мають вигляд:. де j = 1, 2, .... n. то визначник дорівнює сумі двох визначників, у яких всі рядки, крім i -й, такі ж, як в заданому визначнику, а i -я рядок в одному з визначників складається з елементів bij. а в іншому - з елементів cij.

Властивість 8 Якщо одна з рядків визначника є лінійна комбінація інших його рядків, то визначник дорівнює нулю (випливає з послідовного застосування властивостей 7, 6, 5, 4).

Властивість 9 Визначник не змінюється, якщо до елементів однієї з його рядків додаються відповідні елементи іншого, помноженої на одне і те ж число (випливає з властивостей 7 і 6). Узагальнення. визначник не змінюється, якщо до однієї з його рядків додається лінійна комбінація інших його рядків.

Обчислювати визначник, виходячи з його визначення, тобто виписуючи n! його членів і визначаючи їх знаки, було б важко. Розроблено способи, що дозволяють обчислювати визначник n-го порядку через визначники нижчого порядку.

Нехай маємо визначник n-го порядку. Для цілого числа k. вибираємо в визначнику k рядків і k стовпців. Елементи, які стоять на перетині цих рядків і стовпців, утворюють матрицю порядку k. Визначник цієї матриці називається міноромk-го порядку визначника d. Навпаки, можна С і (n-k) стовпців - залишиться мінор k -го порядку. Нижче наведена схема виділення мінору k -го порядку викреслюванням k рядків і k стовпців: