www.wikidata.uk-ua.nina.az

Перестановка Перестановкою скінченної множини X displaystyle X називається впорядкований набір без повторів із її елемен

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

Перестановкою скінченної множини називається впорядкований набір без повторів із її елементів.

Всі 6 перестановок 3 м'ячиків

Перестановка — довільна бієкція . Усього існує (факторіал) різних перестановок, де (потужність множини (кількість елементів у ній)).

Нотація Редагувати

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

У два рядки Редагувати

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

В один рядок Редагувати

Уживанішим у літературі є запис перестановки в один рядок (верхній рядок не пишеться):

Циклічна Редагувати

Циклом перестановки називається така послідовність , що

Приклад:

Перестановка має три цикли:

Циклічний запис перестановки — це запис через її цикли:

Так для перестановки з прикладу справедливим є запис:

Пов'язані означення Редагувати

  • Нерухомий елемент перестановки це елемент Нерухомий елемент є циклом довжини 1.
  • Транспозиція — перестановка, що міняє місцями два елементи. Транспозиція є циклом довжини 2.
  • Декремент перестановки — це кількість елементів мінус кількість циклів. Парність декремента дорівнює парності перестановки.

Група перестановок Редагувати

Перестановки скінченної множини утворюють групу щодо операції множення перестановок (композиції).

Тотожна перестановка Редагувати

Нейтральним елементом в групі перестановок є тотожна перестановка , для якої виконується:

Тотожна перестановка переводить множину саму в себе.

Добуток перестановок Редагувати

Добуток перестановок — це послідовне виконання двох перестановок (композиція): Якщо  — перестановки, то:

Наприклад, нехай маємо

Переставимо стовпці у , щоб її верхній ряд збігався із нижнім рядом

.

Обернений елемент Редагувати

Кожна перестановка має обернену перестановку.

перестановки така що:

Алгоритми на перестановках Редагувати

Алгоритм отримання всіх перестановок Редагувати

Наведений нижче алгоритм дозволяє послідовно отримати всі перестановки скінченної множини. Для зручності будемо вважати, що елементами множини є числа від 1 до n, що записані у масив A.

  1. Спочатку (В масиві записана тотожна перестановка)
  2. Проглядаючи елементи з кінця масиву, знаходимо найбільше таке, що .
    Якщо такого не має, то завершуємо роботу.
  3. Знаходимо максимальне таке, що
  4. Міняємо місцями -й і -й елементи:
  5. Перегортаємо частину масиву з -го по останній (-й) індекси включно:
  6. Отримана нова перестановка. Повертаємося до п. 2.

Аналіз складності алгоритму Редагувати

Кількість елементів, що розглядаються чи опрацьовуються на кроках 3 і 5 не перевищує кількість елементів, що переглядаються на кроці 2. На кроці 4 завжди виконується тільки одна операція обміну елементів. Отже, визначальною для складності алгоритму є кількість операцій на кроці 2. Вона залежить від поточного стану множини і може змінюватися від 1 до n − 1. Для визначення складності алгоритму достатньо оцінити середню кількість операцій на кроці 2.

Кількість перестановок для яких на кроці 2 буде переглядатись рівно елементів така — .

Середня кількість переглядів елементів на кроці 2 для всіх можливих перестановок:

Отже, в середньому на кроці 2 виконується менше ніж три перегляди елементів. Значить, такого ж порядку кількість операцій виконується на кроках 3 і 5. Звідси випливає, що отримання нової перестановки відбувається в середньому за константну кількість операцій , тоді складність алгоритму отримання всіх перестановок буде відповідно .

Приклад роботи Редагувати

Для прикладу отримаємо всі перестановки множини з трьох елементів, розглянемо стани масиву на початку п. 2, а також відповідні індекси :

  1. A = (1, 2, 3) (i = 2, j = 3)
  2. A = (1, 3, 2) (i = 1, j = 3)
  3. A = (2, 1, 3) (i = 2, j = 3)
  4. A = (2, 3, 1) (i = 1, j = 2)
  5. A = (3, 1, 2) (i = 2, j = 3)
  6. A = (3, 2, 1) — завершення алгоритму.

Алгоритм послідовно отримав всі 6 можливих перестановок.

Алгоритм отримання кореня з перестановки Редагувати

Коренем з перестановки називається така перестановка , що .

Справедливе наступне твердження:  — перестановка . Звідси випливає, що . Якщо парне, то  — корінь із перестановки.

, де НСК — найменше спільне кратне, а  — довжина i-го циклу в циклічному записі перестановки . Отже, якщо всі непарні, то k — непарне, а k+1 — парне, і корінь з перестановки гарантовано існує (достатньо просто піднести початкову перестановку до відповідного степеня).

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

Теорема про існування кореня з перестановки Редагувати

Корінь з перестановки існує тоді і тільки тоді, якщо кількість циклів перестановки довжини  — парна.

Доведення Редагувати

Спочатку доведемо необхідність умови. Припустимо існує корінь . Розглянемо циклічне представлення цієї перестановки: .

Якщо i-й цикл має непарну довжину, то при піднесенні перестановки до квадрата, він перейде в цикл  — теж непарної довжини. Тобто якщо в перестановці якийсь елемент належав циклові непарної довжини, то і у квадраті цієї перестановки елемент буде належати циклові непарної довжини.

Якщо ж i-й цикл має парну довжину, то при піднесенні перестановки до квадрата, він перейде у два цикли однакової довжини і .

Цикли парної довжини у квадраті перестановки могли утворитись тільки з циклів парної довжини. А отже, якщо є один цикл парної довжини, то обов'язково існує і інший такої самої довжини.

Доведення достатності випливає з алгоритму знаходження кореня.

Опис алгоритму Редагувати

  1. Представити перестановку в циклічному вигляді.
  2. Перевірити виконання умови теореми. Якщо не виконується, то корінь не існує — завершити роботу.
  3. Перетворити кожен цикл непарної довжини на цикл
  4. Розділити цикли парної довжини на пари рівної довжини. Кожну пару циклів і об'єднати в один цикл

Оцінка складності Редагувати

Кожен із 4 кроків алгоритму може бути виконаний за час , отже загальна складність — .

Приклад використання Редагувати

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

  1. Циклічне представлення
  2. Циклів довжини два, парна кількість, умова теореми виконується.
  3. Перетворимо цикл непарної довжини
  4. Перетворимо пару циклів парної довжини

Шукана перестановка виглядає так: , легко переконатись, що .

Зауваження Редагувати

Наведений алгоритм знаходить тільки один корінь, в загальному ж випадку коренів може бути декілька.

Перестановки з повторенням Редагувати

Розглянемо n елементів m різних типів, причому в кожному типі всі елементи однакові. Тоді перестановки із всіх цих елементів з точністю до порядку розміщення однотипних елементів називаються перестановками з повторенням. Якщо ki — кількість елементів i-го типу, то і кількість можливих перестановок з повтореннями дорівнює мультиноміальному коефіцієнту

Див. також Редагувати

Джерела Редагувати

  • Джозеф Ротман[en]. An Introduction to the Theory of Groups. — 4th. — Springer (Graduate Texts in Mathematics), 1994. — 532 с. — ISBN 978-0387942858.(англ.)
  • И. И. Ежов, А. В. Скороход, М. И. Ядренко. Элементы комбинаторики. Москва: Наука, 1977. — 80 с.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Perestanovkoyu skinchennoyi mnozhini X displaystyle X nazivayetsya vporyadkovanij nabir bez povtoriv iz yiyi elementiv Vsi 6 perestanovok 3 m yachikivPerestanovka dovilna biyekciya p X X displaystyle pi X to X Usogo isnuye n displaystyle n faktorial riznih perestanovok de n X displaystyle n X potuzhnist mnozhini kilkist elementiv u nij Zmist 1 Notaciya 1 1 U dva ryadki 1 2 V odin ryadok 1 3 Ciklichna 2 Pov yazani oznachennya 3 Grupa perestanovok 3 1 Totozhna perestanovka 3 2 Dobutok perestanovok 3 3 Obernenij element 4 Algoritmi na perestanovkah 4 1 Algoritm otrimannya vsih perestanovok 4 1 1 Analiz skladnosti algoritmu 4 1 2 Priklad roboti 4 2 Algoritm otrimannya korenya z perestanovki 4 2 1 Teorema pro isnuvannya korenya z perestanovki 4 2 1 1 Dovedennya 4 2 2 Opis algoritmu 4 2 3 Ocinka skladnosti 4 2 4 Priklad vikoristannya 4 2 5 Zauvazhennya 5 Perestanovki z povtorennyam 6 Div takozh 7 DzherelaNotaciya RedaguvatiDlya zruchnosti perestanovki rozglyadayut nad mnozhinoyu 1 2 n displaystyle 1 2 dots n nbsp bud yaku skinchennu mnozhinu mozhna odnoznachno vidobraziti v cyu mnozhinu U dva ryadki Redaguvati Zapis f 1 2 3 4 5 6 7 8 9 10 2 5 10 4 3 7 1 9 8 6 displaystyle f begin pmatrix 1 amp 2 amp 3 amp 4 amp 5 amp 6 amp 7 amp 8 amp 9 amp 10 2 amp 5 amp 10 amp 4 amp 3 amp 7 amp 1 amp 9 amp 8 amp 6 end pmatrix nbsp oznachaye sho f displaystyle f nbsp perestanovka mnozhini 1 2 10 displaystyle 1 2 dots 10 nbsp i f 1 2 f 2 5 f 10 6 displaystyle f 1 2 f 2 5 dots f 10 6 nbsp kozhne chislo u verhnomu ryadku matrici perevoditsya u vidpovidne chislo v nizhnomu ryadku V odin ryadok Redaguvati Uzhivanishim u literaturi ye zapis perestanovki v odin ryadok verhnij ryadok ne pishetsya f 2 5 10 4 3 7 1 9 8 6 displaystyle f begin pmatrix 2 amp 5 amp 10 amp 4 amp 3 amp 7 amp 1 amp 9 amp 8 amp 6 end pmatrix nbsp ta sama perestanovka sho i v prikladi zapisu u dva ryadki Ciklichna Redaguvati Dokladnishe Ciklichnij zapis kombinatorika Ciklom perestanovki p displaystyle pi nbsp nazivayetsya taka poslidovnist x 1 x 2 x n displaystyle x 1 x 2 dots x n nbsp sho p x 1 x 2 p x 2 x 3 p x n 1 x n p x n x 1 displaystyle pi x 1 x 2 pi x 2 x 3 dots pi x n 1 x n pi x n x 1 nbsp Priklad Perestanovka f 1 2 3 4 5 6 7 8 9 10 2 5 10 4 3 7 1 9 8 6 displaystyle f begin pmatrix 1 amp 2 amp 3 amp 4 amp 5 amp 6 amp 7 amp 8 amp 9 amp 10 2 amp 5 amp 10 amp 4 amp 3 amp 7 amp 1 amp 9 amp 8 amp 6 end pmatrix nbsp maye tri cikli 1 2 5 3 10 6 7 1 displaystyle 1 to 2 to 5 to 3 to 10 to 6 to 7 to 1 nbsp 4 4 displaystyle 4 to 4 nbsp 8 9 8 displaystyle 8 to 9 to 8 nbsp Ciklichnij zapis perestanovki ce zapis cherez yiyi cikli p x 1 1 x n 1 1 x 1 2 x n 2 2 x 1 m x n m m displaystyle pi begin pmatrix x 1 1 amp dots amp x n 1 1 end pmatrix begin pmatrix x 1 2 amp dots amp x n 2 2 end pmatrix dots begin pmatrix x 1 m amp dots amp x n m m end pmatrix nbsp Tak dlya perestanovki z prikladu spravedlivim ye zapis f 1 2 5 3 10 6 7 4 8 9 displaystyle f begin pmatrix 1 amp 2 amp 5 amp 3 amp 10 amp 6 amp 7 end pmatrix begin pmatrix 4 end pmatrix begin pmatrix 8 amp 9 end pmatrix nbsp Pov yazani oznachennya RedaguvatiNeruhomij element perestanovki ce element x X p x x displaystyle x in X mid pi x x nbsp Neruhomij element ye ciklom dovzhini 1 Transpoziciya perestanovka sho minyaye miscyami dva elementi Transpoziciya ye ciklom dovzhini 2 Inversiyeyu v perestanovci p displaystyle pi nbsp nazivayetsya para indeksiv i j displaystyle i j nbsp taka sho 1 i lt j n displaystyle 1 leqslant i lt j leqslant n nbsp ta p i gt p j displaystyle pi i gt pi j nbsp Parnist chisla inversij v perestanovci viznachaye parnist perestanovki Bezlad perestanovka bez neruhomih elementiv Dekrement perestanovki ce kilkist elementiv minus kilkist cikliv Parnist dekrementa dorivnyuye parnosti perestanovki Grupa perestanovok RedaguvatiDokladnishe Simetrichna grupaPerestanovki skinchennoyi mnozhini X displaystyle X nbsp utvoryuyut grupu shodo operaciyi mnozhennya perestanovok kompoziciyi Totozhna perestanovka Redaguvati Nejtralnim elementom v grupi perestanovok ye totozhna perestanovka E displaystyle E nbsp dlya yakoyi vikonuyetsya x X E x x displaystyle forall x in X E x x nbsp Totozhna perestanovka perevodit mnozhinuX displaystyle X nbsp samu v sebe Dobutok perestanovok Redaguvati Dobutok perestanovok ce poslidovne vikonannya dvoh perestanovok kompoziciya Yaksho f g displaystyle f g nbsp perestanovki to c f g x X c x g f x displaystyle c f times g Leftrightarrow forall x in X c x g f x nbsp Napriklad nehaj mayemo A a b c d e f c d a f b e B a b c d e f f e d c b a displaystyle A begin pmatrix a amp b amp c amp d amp e amp f c amp d amp a amp f amp b amp e end pmatrix quad quad B begin pmatrix a amp b amp c amp d amp e amp f f amp e amp d amp c amp b amp a end pmatrix nbsp Perestavimo stovpci u B displaystyle B nbsp shob yiyi verhnij ryad zbigavsya iz nizhnim ryadom A displaystyle A nbsp A B a b c d e f c d a f b e c d a f b e d c f a e b a b c d e f d c f a e b displaystyle A circ B begin pmatrix a amp b amp c amp d amp e amp f c amp d amp a amp f amp b amp e end pmatrix circ begin pmatrix c amp d amp a amp f amp b amp e d amp c amp f amp a amp e amp b end pmatrix begin pmatrix a amp b amp c amp d amp e amp f d amp c amp f amp a amp e amp b end pmatrix nbsp Obernenij element Redaguvati Kozhna perestanovka maye obernenu perestanovku displaystyle forall nbsp perestanovki f f 1 displaystyle f exists f 1 nbsp taka sho f f 1 f 1 f E displaystyle f times f 1 f 1 times f E nbsp dd Algoritmi na perestanovkah RedaguvatiAlgoritm otrimannya vsih perestanovok Redaguvati Navedenij nizhche algoritm dozvolyaye poslidovno otrimati vsi perestanovki skinchennoyi mnozhini Dlya zruchnosti budemo vvazhati sho elementami mnozhini ye chisla vid 1 do n sho zapisani u masiv A Spochatku i A i i displaystyle forall i A i i nbsp V masivi zapisana totozhna perestanovka Proglyadayuchi elementi z kincya masivu znahodimo najbilshe i displaystyle i nbsp take sho A i lt A i 1 displaystyle A i lt A i 1 nbsp Yaksho takogo ne maye to zavershuyemo robotu Znahodimo maksimalne j j gt i displaystyle j j gt i nbsp take sho A j gt A i displaystyle A j gt A i nbsp Minyayemo miscyami i displaystyle i nbsp j i j displaystyle j nbsp j elementi A i A j displaystyle A i leftrightarrow A j nbsp Peregortayemo chastinu masivu z i 1 displaystyle i 1 nbsp go po ostannij n displaystyle n nbsp j indeksi vklyuchno k i 1 i n 1 2 A k A i n 1 k displaystyle forall k overline i 1 lfloor i n 1 2 rfloor A k leftrightarrow A i n 1 k nbsp Otrimana nova perestanovka Povertayemosya do p 2 Analiz skladnosti algoritmu Redaguvati Kilkist elementiv sho rozglyadayutsya chi opracovuyutsya na krokah 3 i 5 ne perevishuye kilkist elementiv sho pereglyadayutsya na kroci 2 Na kroci 4 zavzhdi vikonuyetsya tilki odna operaciya obminu elementiv Otzhe viznachalnoyu dlya skladnosti algoritmu ye kilkist operacij na kroci 2 Vona zalezhit vid potochnogo stanu mnozhini i mozhe zminyuvatisya vid 1 do n 1 Dlya viznachennya skladnosti algoritmu dostatno ociniti serednyu kilkist operacij na kroci 2 Kilkist perestanovok dlya yakih na kroci 2 bude pereglyadatis rivno k displaystyle k nbsp elementiv taka C n k 1 C k 1 2 n k 1 displaystyle C n k 1 cdot C k 1 2 cdot n k 1 nbsp Serednya kilkist pereglyadiv elementiv na kroci 2 dlya vsih mozhlivih perestanovok 1 n k 1 n 1 k C n k 1 C k 1 2 n k 1 displaystyle frac 1 n sum k 1 n 1 k cdot C n k 1 cdot C k 1 2 cdot n k 1 nbsp 1 n k 1 n 1 k n k 1 n k 1 k 1 2 k 1 n k 1 1 2 k 0 n 2 k 1 k lt 1 2 k 0 k 1 k e lt 3 displaystyle frac 1 n sum k 1 n 1 k cdot frac n k 1 n k 1 cdot frac k 1 2 cdot k 1 cdot n k 1 frac 1 2 sum k 0 n 2 frac k 1 k lt frac 1 2 sum k 0 infty frac k 1 k e lt 3 nbsp Otzhe v serednomu na kroci 2 vikonuyetsya menshe nizh tri pereglyadi elementiv Znachit takogo zh poryadku kilkist operacij vikonuyetsya na krokah 3 i 5 Zvidsi viplivaye sho otrimannya novoyi perestanovki vidbuvayetsya v serednomu za konstantnu kilkist operacij O 1 displaystyle O 1 nbsp todi skladnist algoritmu otrimannya vsih perestanovok bude vidpovidno O n displaystyle O n nbsp Priklad roboti Redaguvati Dlya prikladu otrimayemo vsi perestanovki mnozhini z troh elementiv rozglyanemo stani masivu na pochatku p 2 a takozh vidpovidni indeksi i j displaystyle i j nbsp A 1 2 3 i 2 j 3 A 1 3 2 i 1 j 3 A 2 1 3 i 2 j 3 A 2 3 1 i 1 j 2 A 3 1 2 i 2 j 3 A 3 2 1 zavershennya algoritmu Algoritm poslidovno otrimav vsi 6 mozhlivih perestanovok Algoritm otrimannya korenya z perestanovki Redaguvati Korenem z perestanovki p displaystyle pi nbsp nazivayetsya taka perestanovka ps displaystyle psi nbsp sho ps 2 p displaystyle psi 2 pi nbsp Spravedlive nastupne tverdzhennya p displaystyle forall pi nbsp perestanovka k N p k E displaystyle exists k in N pi k E nbsp Zvidsi viplivaye sho p k 1 p displaystyle pi k 1 pi nbsp Yaksho k 1 displaystyle k 1 nbsp parne to p k 1 2 ps displaystyle pi frac k 1 2 psi nbsp korin iz perestanovki k H C K n 1 n 2 n l displaystyle k HCK n 1 n 2 n l nbsp de NSK najmenshe spilne kratne a n i displaystyle n i nbsp dovzhina i go ciklu v ciklichnomu zapisi perestanovki p displaystyle pi nbsp Otzhe yaksho vsi n i displaystyle n i nbsp neparni to k neparne a k 1 parne i korin z perestanovki garantovano isnuye dostatno prosto pidnesti pochatkovu perestanovku do vidpovidnogo stepenya Cej rozv yazok neprijnyatnij yaksho perestanovka maye cikli parnoyi dovzhini Ale ce ne oznachaye sho taki perestanovki vzagali ne mayut koreniv Teorema pro isnuvannya korenya z perestanovki Redaguvati Korin z perestanovki isnuye todi i tilki todi yaksho k N displaystyle forall k in N nbsp kilkist cikliv perestanovki dovzhini 2 k displaystyle 2k nbsp parna Dovedennya Redaguvati Spochatku dovedemo neobhidnist umovi Pripustimo isnuye korin ps ps 2 p displaystyle psi psi 2 pi nbsp Rozglyanemo ciklichne predstavlennya ciyeyi perestanovki ps x 1 1 x l 1 1 x 1 m x l m m displaystyle psi x 1 1 x l 1 1 x 1 m x l m m nbsp Yaksho i j cikl x 1 x l i displaystyle x 1 x l i nbsp maye neparnu dovzhinu to pri pidnesenni perestanovki do kvadrata vin perejde v cikl x 1 x 3 x 2 t 1 x l i x 2 x 4 x 2 p x l i 1 displaystyle x 1 x 3 x 2t 1 x l i x 2 x 4 x 2p x l i 1 nbsp tezh neparnoyi dovzhini Tobto yaksho v perestanovci yakijs element nalezhav ciklovi neparnoyi dovzhini to i u kvadrati ciyeyi perestanovki element bude nalezhati ciklovi neparnoyi dovzhini Yaksho zh i j cikl x 1 x l i displaystyle x 1 x l i nbsp maye parnu dovzhinu to pri pidnesenni perestanovki do kvadrata vin perejde u dva cikli odnakovoyi dovzhini x 1 x 3 x 2 t 1 x l i 1 displaystyle x 1 x 3 x 2t 1 x l i 1 nbsp i x 2 x 4 x 2 p x l i displaystyle x 2 x 4 x 2p x l i nbsp Cikli parnoyi dovzhini u kvadrati perestanovki mogli utvoritis tilki z cikliv parnoyi dovzhini A otzhe yaksho ye odin cikl parnoyi dovzhini to obov yazkovo isnuye i inshij takoyi samoyi dovzhini Dovedennya dostatnosti viplivaye z algoritmu znahodzhennya korenya Opis algoritmu Redaguvati Predstaviti perestanovku v ciklichnomu viglyadi Pereviriti vikonannya umovi teoremi Yaksho ne vikonuyetsya to korin ne isnuye zavershiti robotu Peretvoriti kozhen cikl neparnoyi dovzhini x 1 x l displaystyle x 1 dots x l nbsp na cikl x 1 x l 1 2 1 x 2 x l 1 2 2 x k x l 1 2 k x l 1 2 1 x l x l 1 2 displaystyle x 1 x frac l 1 2 1 x 2 x frac l 1 2 2 dots x k x frac l 1 2 k dots x frac l 1 2 1 x l x frac l 1 2 nbsp Rozdiliti cikli parnoyi dovzhini na pari rivnoyi dovzhini Kozhnu paru cikliv x 1 1 x l 1 displaystyle x 1 1 x l 1 nbsp i x 1 2 x l 2 displaystyle x 1 2 x l 2 nbsp ob yednati v odin cikl x 1 1 x 1 2 x 2 1 x 2 2 x k 1 x k 2 x l 1 x l 2 displaystyle x 1 1 x 1 2 x 2 1 x 2 2 dots x k 1 x k 2 dots x l 1 x l 2 nbsp Ocinka skladnosti Redaguvati Kozhen iz 4 krokiv algoritmu mozhe buti vikonanij za chas O n displaystyle O n nbsp otzhe zagalna skladnist O n displaystyle O n nbsp Priklad vikoristannya Redaguvati Dlya prikladu znajdemo korin z perestanovki p 1 2 3 4 5 6 7 3 4 1 7 6 5 2 displaystyle pi begin pmatrix 1 amp 2 amp 3 amp 4 amp 5 amp 6 amp 7 3 amp 4 amp 1 amp 7 amp 6 amp 5 amp 2 end pmatrix nbsp Ciklichne predstavlennya p 2 4 7 1 3 5 6 displaystyle pi begin pmatrix 2 amp 4 amp 7 end pmatrix begin pmatrix 1 amp 3 end pmatrix begin pmatrix 5 amp 6 end pmatrix nbsp Cikliv dovzhini dva parna kilkist umova teoremi vikonuyetsya Peretvorimo cikl neparnoyi dovzhini 2 4 7 2 7 4 displaystyle begin pmatrix 2 amp 4 amp 7 end pmatrix to begin pmatrix 2 amp 7 amp 4 end pmatrix nbsp Peretvorimo paru cikliv parnoyi dovzhini 1 3 5 6 1 5 3 6 displaystyle begin pmatrix 1 amp 3 end pmatrix begin pmatrix 5 amp 6 end pmatrix to begin pmatrix 1 amp 5 amp 3 amp 6 end pmatrix nbsp Shukana perestanovka viglyadaye tak ps 1 2 3 4 5 6 7 5 7 6 2 3 1 4 displaystyle psi begin pmatrix 1 amp 2 amp 3 amp 4 amp 5 amp 6 amp 7 5 amp 7 amp 6 amp 2 amp 3 amp 1 amp 4 end pmatrix nbsp legko perekonatis sho ps 2 p displaystyle psi 2 pi nbsp Zauvazhennya Redaguvati Navedenij algoritm znahodit tilki odin korin v zagalnomu zh vipadku koreniv mozhe buti dekilka Perestanovki z povtorennyam RedaguvatiRozglyanemo n elementiv m riznih tipiv prichomu v kozhnomu tipi vsi elementi odnakovi Todi perestanovki iz vsih cih elementiv z tochnistyu do poryadku rozmishennya odnotipnih elementiv nazivayutsya perestanovkami z povtorennyam Yaksho ki kilkist elementiv i go tipu to k 1 k 2 k m n displaystyle k 1 k 2 dots k m n nbsp i kilkist mozhlivih perestanovok z povtorennyami dorivnyuye multinomialnomu koeficiyentu n k 1 k 2 k m n k 1 k 2 k m displaystyle textstyle binom n k 1 k 2 dots k m frac n k 1 k 2 dots k m nbsp Div takozh RedaguvatiPsevdovipadkova perestanovka Pidstanovka Algoritm sortuvannya RozmishennyaDzherela RedaguvatiDzhozef Rotman en An Introduction to the Theory of Groups 4th Springer Graduate Texts in Mathematics 1994 532 s ISBN 978 0387942858 angl I I Ezhov A V Skorohod M I Yadrenko Elementy kombinatoriki Moskva Nauka 1977 80 s Otrimano z https uk wikipedia org w index php title Perestanovka amp oldid 36918028