МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах
РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ" ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах Гендерна антидискримінаційна експертиза може зробити нас моральними рабами ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів Контакти
Тлумачний словник |
|
|||||||
Узагальнення другої форми принципу математичної індукціїЯкщо деяке твердження Т правильне для натурального числа і якщо з припущення, що воно правильне для всіх натуральних чисел, менших k, випливає його правильність і для числа k, то твердження Т правильне для будь-якого натурального числа.
§2. Підстановки а) Перестановки
Всяке розташування чисел 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 символів є i1,i2,…,in, де кожне із ik є одним із чисел 1,2,…,n, причому жодне з чисел не зустрічається двічі. В ролі i1 можна взяти довільне із чисел 1,2,…,n. Це дасть n різних варіантів. Якщо ж i1 вже вибрано, то в ролі i2 можна взяти тільки n-1 із чисел, що залишилися. Тоді кількість різних способів вибрати символи i1 та i2 дорівнюватиме n(n-1). Далі аналогічні міркування. ▲
2. Від довільної перестановки із n символів можна перейти до будь-якої іншої перестановки із тих же елементів з допомогою декількох транспозицій. Ця властивість, очевидно, випливає із того, що всі n! перестановок із символів можна розмістити в такому порядку, що кожна наступна отримана із попередньої однією транспозицією, причому починати можна з довільної перестановки. ▲
3. Кожна транспозиція змінює парність перестановки. Якщо транспоновані символи i та j є сусідніми, тобто перестановка має вигляд …, i,j,…, то в результаті транспозиції отримаємо перестановку …, j,i,…, в якій символи i та j утворюють із нерухомими символами ті ж інверсії, що й у попередній. Від переставляння символів i та j кількість інверсій зміниться на одну (якщо інверсії не було, то з’явиться, якщо ж була, то зникне), що і змінить парність перестановки. Якщо ж між транспонованими символами i та j розміщені s символів, тобто перестановка має вигляд …,i,k1,k2,…,ks,j,…,то транспозицію символів i та j можна отримати в результаті 2s+1 транспозицій сусідніх елементів (s для переміщення i на місце ks,1 для переставлення місцями і та j, s для переміщення j з позиції ks на місце i), після чого утвориться перестановка …,j,k1,k2,…,ks,i,… ,яка матиме протилежну парність до початкової. 4. При n³2 кількість парних перестановок із n символів дорівнює кількості непарних, тобто дорівнює n! Дійсно, якщо впорядкувати усі перестановки із n символів так, що кожна отримується із попередньої однією транспозицією, то сусідні перестановки матимуть протилежні парності, а число n! парне.
б) Підстановки
Дві перестановки із n символів, записані одна під одною, визначають деяке взаємно однозначне відображення множини перших n натуральних чисел на себе. Довільне взаємно однозначне відображення А множини перших n натуральних чисел на себе називається підстановкою n-гостепеня.Символічний запис: Тут αi – число, в яке при перестановці А переходить число i, і=1,2,…,n. Читають так: при підстановці А число і1 переходить в , і2 – в ,…, іn – в . Від одного запису підстановки А до іншого можна перейти з допомогою декількох транспозицій стовпчиків. Приклад.
, , .
При цьому можна отримати запис вигляду (2.1), при якому різні підстановки відрізняються одна від одної тільки нижніми перестановками, звідки випливає, що кількість підстановок n-го степеня дорівнює кількості перестановок із n символів, тобто дорівнює n!Підстановка називається тотожньою або одиничною. Підстановка називається парною,якщо парності верхньої і нижньої її перестановок співпадають або сума інверсій у верхній і нижній перестановках є парною. В іншому випадку підстановка непарна. Кількість непарних підстановок n-го степеня дорівнює кількості парних, тобто дорівнює n!Цей висновок випливає із можливості запису довільної перестановки у вигляді (2.1) і властивості 4 перестановок з n елементів. Добуткомдвох підстановок n-го степеня називається підстановка n-го степеня, отримана в результаті послідовного виконання даних підстановок. Приклад.
=.
Множення підстановок n-го степеня при n3 некомутативне. Приклад. =
(порівняти з попереднім). Множення підстановок асоціативне,тобто (АВ)С=А(ВС). Дійсно, якщо символ і1 при підстановці А переходить в і2, символ і2 при підстановці В переходить в і3, а і3 при підстановці С переходить в і4, то при підстановці АВ символ і1 переходить в і3,при підстановці ВС символ і2 переходить в і4, тому при обох підстановках (АВ)С та А(ВС) символ і1 переходить в символ і4. Ясно, що для будь-якої підстановки А: АЕ=ЕА=А. Оберненою для підстановки А називається така підстановка А-1 тогож степеня, що АА-1 = А-1А = Е. Очевидним є те, що оберненою для підстановки A=є підстановка А-1=, отримана із А переставленням нижнього і верхнього рядків. Циклічною підстановкою або циклом довжиною k називається така підстановка, при повторенні якої k разів кожен з її символів переходить в себе. Приклад.
підстановка 8-го степеня має цикл (2836) довжиною 4.
Читайте також:
|
||||||||
|