Перестановки і транспозиції, визначники
Сукупність чисел серед яких немає рав-них і кожне з яких є одне з чисел 1, 2. п, називаються ється перестановкою цих чисел. Перестановка 1, 2. п. Називаються ється нормальною.
У безлічі з п чисел загальна кількість перестановок одно п !.
Кажуть, що в даній перестановці числа i, j утворюють інверсію, якщо i> j. але i стоїть в перестановці раніше j.
Наприклад, перестановка 15243. Числа 5, 2 утворюють інверсію.
Підрахунок числа інверсій роблять у такий спосіб. Спочатку підраховуємо число елементів, що стоять попереду одиниці - всі ці елементи і тільки вони утворюють інверсію з одиницею. Викреслюємо одиницю і підраховуємо число елементів попереду двійки - це будуть всі ті елементи, які утворюють інверсії з двійкою (не рахуючи викресленої одиниці). Потім викреслюємо двійку і підраховуємо число елементів перед трійкою і т.д. Сума всіх отриманих чисел і буде дорівнює числу інверсій. Число всіх інверсій в перестановці позначимо.
Перестановка називається парною, якщо її числа склад-ляють парна кількість інверсій, і нечетной- в іншому випадку.
Транспозицией називається перетворення перестановки, при якому міняються місцями будь-які два числа, які не орга-тельно стоять поруч.
Теорема 4.1Всякая транспозиція змінює парність перестановки.
# 9633; Розглянемо спочатку випадок, коли міняються місцями два сусідніх елемента і перестановки Після транспозиції елементів і отримаємо переста-новку Так як перестановки відрізняються один від одного тільки взаємним розташуванням елементів і (а взаємне розташування кожного з цих елементів і якогось іншого, так само як і взаємне располо-ються будь-яких двох з інших елементів, залишилися колишніми), то число інверсій в другій перестановці на одиницю більше або на одиницю менше числа інверсій в першій перестановці, і значить, одна з цих пере-стано ок парна, а інша - непарна.
Загальний випадок. Нехай міняються місцями елементи і перестановки між якими стоять ще k елементів. Можна виконати транспозицию елементів і за допомогою декількох транспозиція поруч стоять елементів: поміняємо місцями спочатку с, потім з і т. Д. Нарешті, з ck (при цьому зробимо k транспозиція поруч стоять елементів); потім поміняємо місцями і (ще одна транспозиція) і, нарешті, поміняємо місцями послідовно с, с і так далі, до (ще k транспозиція поруч стоять елементів). У підсумку стане на місце і навпаки. При кожній такій транспозиції парність перестановки змінюється. Так як вона змінить-ся непарне число раз (2k + 1), тому не-парна перестановка зробиться парної, а парна - Ні-парної. # 9632;
Слідство. Число парних перестановок дорівнює числу непарних і дорівнює 0,5 n!
# 9633; Нехай з n! перестановок з n елементів p перестановок парні і q непарні. Сдела третьому в кожній парній перестановці одну і ту ж транс-позицію, наприклад, поміняємо місцями перші два еле-мента. Тоді кожна парна перестановка перетвориться в непарну, при цьому всі p отриманих при цьому непарних перестановок будуть різними. А так як загальне число непарних перестановок з n елементів-тов, за припущенням, так само q, то p
Всі n! перестановок з n чисел можна розташувати в такому порядку, що кожна наступна буде виходити з пре-дидущей за допомогою однієї транспозиції, причому починати можна з будь-якої перестановки.
Визначником n-гопорядка, відповідним квадрат-ної матриці порядку n, називається алгебраїчна сума n! членів, складена в такий спосіб. Членами визначника служать всілякі твори по n елементів матриці, узятих по одному в кожному рядку і кожному стовпці. Член бе-рется зі знаком плюс, якщо індекси стовпців його елементів об-роззують парну перестановку за умови, що самі елементи розташовані в порядку зростання номерів рядків, і зі знаком мінус - в іншому випадку і позначається:
Визначником першого порядку є величина елемента:
Визначником другого порядку дорівнює добутку елементів на головній діагоналі мінус твір елементів на побічної діагоналі:
Визначник третього порядку, обчислений за правилом Саррюс