Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

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



План:


Введення

В комбінаториці перестановка - це упорядкований набір чисел 1, 2, \ ldots, n, зазвичай трактований як біекція на безлічі \ {1, 2, \ ldots, n \} , Яка числа i ставить відповідність i-й елемент з набору. Число n при цьому називається порядком перестановки.

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


1. Властивості

P_n = A_n ^ n = n! = 1 \ cdot 2 \ cdot \ dots \ cdot n.
  • Композиція визначає операцію твори на перестановках одного порядку: (\ Pi \ cdot \ sigma) (k) = \ pi (\ sigma (k)). Щодо цієї операції безліч перестановок порядку n утворює групу, яку називають симетричної і зазвичай позначають S n .
  • Будь група є підгрупою групи перестановок безлічі елементів цієї групи ( теорема Келі). При цьому кожен елемент a \ in G зіставляється з перестановкою π a , Що задається тотожністю \ Pi_a (g) = a \ circ g, де g - довільний елемент групи G, а \ Circ - Групова операція.

2. Пов'язані визначення

  • Носій перестановки \ Pi \ colon X \ to X - Це підмножина безлічі X , Яке визначається як \ Operatorname {supp} (\ pi) = \ {x \ in X \ mid \ pi (x) \ ne x \}.
  • Нерухомою точкою перестановки π є всяка нерухома точка відображення \ Pi \ colon X \ to X , Тобто елемент безлічі \ {X \ in X \ mid \ pi (x) = x \}. Безліч всіх нерухомих точок перестановки π є доповненням її носія в X .
  • Інверсією в перестановці π порядку n називається всяка пара індексів i, j така, що 1 \ leqslant i <j \ leqslant n і π (i)> π (j) . Парність числа інверсій в перестановці визначає парність перестановки.
  • Знак перестановки визначається як +1 для парної перестановки і -1 для непарної, що виражається формулою sgn (σ) = (- 1) N (σ) , Де N (σ) - Кількість інверсій в перестановці σ . Знак перестановки σ може бути також визначений як sgn (σ) = (- 1) m , Де m - кількість транспозицій в розкладанні σ у твір транспозицій. Незважаючи на те, що таке розкладання не єдино, парність кількості транспозицій у всіх розкладах σ одна й та сама, і тому знак перестановки коректно визначений.

2.1. Спеціальні типи перестановок

  • Інволюція - перестановка τ, яка є зворотною самої себе, тобто \ Tau \ cdot \ tau = id.
  • Безлад - перестановка без нерухомих точок.
  • Циклом довжини \ Ell називається така підстановка π, яка тотожна по всьому безлічі X, крім підмножини \ {X_1, x_2, \ dots, x_ \ ell \} \ subset X і \ Pi (x_ \ ell) = x_1, \ pi (x_i) = x_ {i +1}. Позначається (X_1, x_2, \ dots, x_ \ ell).
  • Транспозиція - перестановка елементів множини X , Яка міняє місцями два елементи. Транспозиція є циклом довжини 2.

2.2. Підстановки і твори циклів

Перестановка π безлічі X може бути записана у вигляді підстановки, наприклад:

\ Begin {pmatrix} x_1 & x_2 & x_3 & \ dots & x_n \ \ y_1 & y_2 & y_3 & \ dots & y_n \ end {pmatrix},

де \ {X_1, \ dots, x_n \} = \ {y_1, \ dots, y_n \} = X і π (x i) = y i.

Перестановку також можна записати у вигляді добутку непересічних циклів, причому єдиним чином з точністю до порядку проходження циклів у творі. Наприклад:

(1, 5, 2) (3, 6) (4) = \ begin {pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \ \ 5 & 1 & 6 & 4 & 2 & 3 \ end {pmatrix} .

3. Випадкова перестановка

Випадкової перестановкою називається випадковий вектор \ Xi = (\ xi_1, \ ldots, \ xi_n), всі елементи якого приймають натуральні значення від 1 до n, і при цьому ймовірність збігу будь-яких двох елементів дорівнює 0.

Незалежної випадкової перестановкою називається така випадкова перестановка ξ , Для якої

P \ {\ xi = \ sigma \} = \ frac {p_ {1 \ sigma (1)} \ ldots p_ {n \ sigma (n)}} {\ sum \ limits_ {\ pi \ in S_n} p_ {1 \ pi (1)} \ ldots p_ {n \ pi (n)}}

для деяких p i j, таких що

\ Forall i (1 \ leqslant i \ leqslant n): p_ {i1} + \ ldots + p_ {in} = 1
\ Sum \ limits_ {\ pi \ in S_n} p_ {1 \ pi (1)} \ ldots p_ {n \ pi (n)}> 0.

Якщо при цьому p i j не залежать від i , То перестановку ξ називають однаково розподіленою. Якщо ж немає залежності від j , Тобто \ Scriptstyle \ forall i, j (1 \ le i, j \ le n): p_ {ij} = 1 / n, то ξ називають однорідною.


Література

  • Дональд Кнут Мистецтво програмування, том 3. Сортування і пошук = The Art of Computer Programming, vol.3. Sorting and Searching - 2-е вид. - М .: "Вільямс", 2007. - С. 824. - ISBN 0-201-89685-0.

Примітки

  1. Віленкін Н. Я. Глава III. Комбінаторика кортежів і множин. Розміщення з повтореннями / / Популярна комбінаторика - www.math.ru / lib / book / djvu / combinatorika.djvu - М .: Наука, 1975. - С. 80. - 208 с.
  2. Теорія конфігурацій і теорія перерахувань - combinatorica.narod.ru / third.html
  3. Глава 3. Елементи комбінаторики - www.mathelp.spb.ru/book2/tv3.htm. / / Лекції з теорії ймовірностей.
  4. http://www.brain2life.com/book/160.html - www.brain2life.com/book/160.html Дональд Е. Кнут - Мистецтво програмування. Том 1. Основні алгоритми. 1.2.5. Перестановки і факторіали

Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Безлад (перестановка)
© Усі права захищені
написати до нас