Узагальнення другої форми принципу математичної індукції

а) Перестановки

Всяке розташування чисел 1,2,…,n в деякому визначеному порядку називається перестановкоюіз n чисел (чи n символів).

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

Вважається, що числа i та j утворюють в даній перестановці інверсію, якщо i>j, але i знаходиться в цій перестановці раніше за j. Перестановка називається парною, якщо її символи утворюють парну кількість інверсій, і непарною– в протилежному випадку. Наприклад, перестановка (2,3,1,4,5) є парною (дві інверсії), а (2,3,1,5,4) – непарною (три інверсії).

Властивості:

1. Кількість різних перестановок із n символів дорівнює добутку 1·2·…·n = n!

Дійсно, загальний вигляд перестановки із n символів є i₁,i₂,…,i_n, де кожне із i_k є одним із чисел 1,2,…,n, причому жодне з чисел не зустрічається двічі. В ролі i₁ можна взяти довільне із чисел 1,2,…,n. Це дасть n різних варіантів. Якщо ж i₁ вже вибрано, то в ролі i₂ можна взяти тільки n-1 із чисел, що залишилися. Тоді кількість різних способів вибрати символи i₁ та i₂ дорівнюватиме n(n-1). Далі аналогічні міркування. ▲

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

Ця властивість, очевидно, випливає із того, що всі n! перестановок із символів можна розмістити в такому порядку, що кожна наступна отримана із попередньої однією транспозицією, причому починати можна з довільної перестановки. ▲

3. Кожна транспозиція змінює парність перестановки.

Якщо транспоновані символи i та j є сусідніми, тобто перестановка має вигляд …, i,j,…, то в результаті транспозиції отримаємо перестановку …, j,i,…,

в якій символи i та j утворюють із нерухомими символами ті ж інверсії, що й у попередній. Від переставляння символів i та j кількість інверсій зміниться на одну (якщо інверсії не було, то з’явиться, якщо ж була, то зникне), що і змінить парність перестановки.

Якщо ж між транспонованими символами i та j розміщені s символів, тобто перестановка має вигляд …,i,k₁,k₂,…,k_s,j,…,то транспозицію символів i та j можна отримати в результаті 2s+1 транспозицій сусідніх елементів (s для переміщення i на місце k_s,1 для переставлення місцями і та j, s для переміщення j з позиції k_s на місце i), після чого утвориться перестановка …,j,k₁,k₂,…,k_s,i,… ,яка матиме протилежну парність до початкової.

4. При n³2 кількість парних перестановок із n символів дорівнює кількості непарних, тобто дорівнює n!

Дійсно, якщо впорядкувати усі перестановки із n символів так, що кожна

отримується із попередньої однією транспозицією, то сусідні перестановки матимуть протилежні парності, а число n! парне.

б) Підстановки

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

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

Тут α_i – число, в яке при перестановці А переходить число i, і=1,2,…,n. Читають так: при підстановці А число і₁ переходить в , і₂ – в ,…, і_n – в .

Від одного запису підстановки А до іншого можна перейти з допомогою декількох транспозицій стовпчиків.

Приклад.

, , .

При цьому можна отримати запис вигляду (2.1),

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

Підстановка називається парною,якщо парності верхньої і нижньої її перестановок співпадають або сума інверсій у верхній і нижній перестановках є парною. В іншому випадку підстановка непарна.

Кількість непарних підстановок n-го степеня дорівнює кількості парних, тобто дорівнює n!Цей висновок випливає із можливості запису довільної перестановки у вигляді (2.1) і властивості 4 перестановок з n елементів.

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

Приклад.

=.

Множення підстановок n-го степеня при n3 некомутативне.

Приклад.

=

(порівняти з попереднім).

Множення підстановок асоціативне,тобто (АВ)С=А(ВС). Дійсно, якщо символ і₁ при підстановці А переходить в і₂, символ і₂ при підстановці В переходить в і₃, а і₃ при підстановці С переходить в і₄, то при підстановці АВ символ і₁ переходить в і₃,при підстановці ВС символ і₂ переходить в і₄, тому при обох підстановках (АВ)С та А(ВС) символ і₁ переходить в символ і_4.

Ясно, що для будь-якої підстановки А: АЕ=ЕА=А.

Оберненою для підстановки А називається така підстановка А^-1 тогож степеня, що АА^-1 = А^-1А = Е.

Очевидним є те, що оберненою для підстановки A=є підстановка А^-1=, отримана із А переставленням нижнього і верхнього рядків.

Циклічною підстановкою або циклом довжиною k називається така підстановка, при повторенні якої k разів кожен з її символів переходить в себе.

Приклад.

підстановка 8-го степеня має цикл (2836) довжиною 4.