Изменения
→Умножение перестановок
{{Определение
|definition=
'''Умножением''' (англ. ''multiplication'') или '''композицией''' (англ. ''composition'') перестановок,представленных в виде целочисленных функций <tex> a_i </tex>, где <tex>i - </tex> позиция элемента, а <tex> a_i </tex> — его номер, называется перестановка, получаемая по следующему правилу:
<tex> (ab)_i = a_b_{b_ia_i} </tex>
}}
Доказывается простым раскрытием скобок.
# <tex> (a(bc))_i = a_{(bc)_i_{a_i} = a_c_{b_{c_ia_i}} </tex># <tex> ((ab)c)_i = c_{(ab)_{c_i_i} = a_c_{b_{c_ia_i}} </tex>
}}
Перед прочтением примера перемножения перестановок рекомендуем познакомиться с циклами в данной статье: [[Действие перестановки на набор из элементов, представление в виде циклов]]
===Пример===
<tex> a = {2, 5, 6, 3, 1, 4} = (1, 2, 5)(3, 6, 4) </tex>
<tex> b = {4, 1, 3, 6, 5, 2} = (1, 4, 6, 52) </tex>
<tex> ab = {a_4, a_1, a_3, a_6, a_5, a_2} = {3, 2, 6, 4, 1, 5} </tex>
|definition=
'''Обратнойперестановкой''' (англ. ''inverse permutation' перестановкой ') <tex> a^{-1} </tex> к перестановке <tex> a </tex> называется такая перестановка, что:
<tex> (a^{-1}a)_i = (aa^{-1})_i = i </tex>
}}
{{Утверждение
|statement=
Для каждой перестановки существует перестановка, обратная ей.
|proof=
Пусть дана перестановка <tex> a </tex>, построим обратную ей перестановку <tex> a^{-1}</tex>: если <tex> a_x = y </tex>, то <tex> a^{-1}_y = x </tex>. Очевидно, что данная перестановка является обратной к <tex> a </tex>.
}}
Также обратная перестановка единственна. Это следует из того, что для каждой <tex> i </tex>-ой позиций в исходной перестановке однозначно определяется <tex> j </tex>-ая позиций в обратной перестановке, значение которой есть <tex> i </tex>
{{Определение
|id = def_involution
|definition=
Перестановка, равная своей обратной, называется '''инволюцией''' (англ. ''involution''):
<tex> a_i = a^{-1}_i \Rightarrow (aa ^{-1})_i = (aa)_i = a_{a_i} = i </tex>, то есть её представление в виде циклов не содержит цикла, размер которого больше двух.
Количество инволюционных перестановок длины <tex>n\geqslant 2 </tex> может быть получено по формуле: <tex> I(n) = I(n-1)+(n-1)\cdot I(n-2) </tex>, где <tex> I(0) = I(1) = 1. </tex>
|proof=
Докажем формулу по '''индукции'''. '''Базой''' являются <tex> I(0) = I(1) = 1 </tex>. '''Предположим''', что для всех <tex> I(i) </tex>, где <tex> i < n</tex>, <tex> n > 1 </tex>, формула верна. Рассмотрим перестановку длины <tex> n </tex> и попробуем найти количество инволюций этой длины. Существует <tex> I(n-1)</tex> инволюций, при <tex>a_n = n </tex>. Число (у которых последний элемент представляет собой цикл длины <tex> 1 </tex>), а число инволюцийдлины <tex> n </tex>, содержащих в своём представлении в виде циклов цикл <tex>(j,n)</tex>, где <tex> 1\leq leqslant j\leq leqslant n-1 </tex>, <tex> (n-1)\cdot I(n-2)</tex>(так как при фиксированных <tex> j </tex> и <tex> n </tex> имеем <tex> I(n-2) </tex> перестановок оставшихся элементов, которые не нарушают свойств инволюции). ИмеемТаким образом, что <tex> I(n) = I(n-1)+(n-1)\cdot I(n-2). </tex>
}}
|definition=
Перестановка, содержащая чётное количество инверсий, называется '''чётной'''(англ. ''even permutation''), в противном случае <tex> - </tex> '''нечётной'''(англ. ''odd permutation'').
}}
|definition=
Перестановка, меняющая местами только два элемента, называется '''транспозицией''' (англ. ''transposition'').
}}
|proof=
Для элементов, стоящих рядом, истинность утверждения очевидна: их взаимное расположение относительно других элементов не изменилось, а транспозиция этих чисел изменяет количество инверсий на единицу. Пусть теперь между перемещаемыми элементами <tex> a </tex> и <tex> b </tex> находятся <tex> d </tex> элементов, то есть перестановка имеет вид: <tex> ... \ldots </tex> , <tex> a, s_1, s_2, ...\ldots, s_d, b, ... \ldots </tex>. Сначала поменяем последовательно <tex> a </tex> с числами <tex> s_1, s_2, ...\ldots, s_d, b </tex>, а затем число <tex>b</tex> с рядом стоящими <tex> s_d, s_d-1, ...\ldots, s_1 </tex>. В итоге мы выполним <tex> 2\cdot d + 1 </tex> транспозиций рядом стоящих элементов, то есть чётность перестановки изменится.
}}
===Получение обратной перестановки===
Пусть в массиве <tex> p[i] </tex> содержится перестановка, длины <tex> n </tex>, тогда в массиве op[i], после выполнения алгоритма, будет содержаться обратная перестановка. for(i = 0; i < n; i++) for(j = 0; j < n; j++) if(p[j] == i + 1) op[i] = j + 1; При представлении перестановки в виде циклов обратную перестановку можно легко получить, инвертировав все ребра в циклах. массиве <tex> a = (1, 3, 2), (4, 5) \Rightarrow a^{-1} = (1, 2, 3), (4, 5) rep </tex>будет содержаться перестановка, обратная ей. Отсюда следует более эффективный алгоритм '''fun''' reversePerm(приведена in-place версия)p : boolean'''int[] visited = new boolean''', rep : '''int[n];''') '''for (int ''' i = 0; i < 1 '''to''' n; ++i) if (visitedrep[i]) continue; // Reverse the cycle starting at i int last = i; int j = p[i]; while (true) int next = p[j]; p[j] = last; visited[j] = true; if (j == i) break; last = j; j = next;
==Группа перестановок==
{{Определение
|definition=
'''Группой''' (англ. ''group'') называется множество <tex> M </tex> с заданной на нём бинарной операцией <tex> \circ: МM\times M \longrightarrow M</tex>, удовлетворяющей следующим свойствам:
# <tex> (g_1 \circ g_2) \circ g_3 = g_1 \circ (g_2 \circ g_3) </tex> — ассоциативность соответствующей бинарной операции.
{{Утверждение
|statement=
Множество перестановок с <tex> n </tex> элементами с операцией умножения является группой (часто группу перестановок называют '''симметрической''' (англ. ''symmetric group''), и обозначают <tex> S_n </tex>).
|proof=
Свойства <tex>1 </tex> и <tex>3 </tex> (ассоциативность умножения и существование обратной перестановки для любой из перестановок) доказаны выше, а в качестве нейтрального элемента выступает тождественная перестановка (<tex> \pi_i = i </tex>).
}}
{{Определение
|definition=
'''Группа чётных перестановок''' (англ. ''alternating group'') <tex> A_n </tex> является подгруппой симметричной группы перестановок, образованной всеми чётными перестановками. Композиция не выводит из группы, так как если представить каждую перестановку группы в виде чётного числа транспозиций и перемножить их, чётность не изменится.
}}
}}
==ПодстановкаГруппа подстановок==
{{Определение
|definition=
'''Подстановкой''' (англ. ''substitution'') называется всякое взаимно однозначное отображение <tex> A </tex> множества первых <tex>n</tex> натуральных чисел на себя.
}}
Всякая подстановка <tex>A </tex> может быть записана при помощи двух перестановок, подписанных одна под другой:
<tex> A = \begin{pmatrix} q_1 & q_2 & ... \ldots & q_n \\ a_{k_1} & a_{k_2} & ... \ldots & a_{k_n} \end{pmatrix} </tex>
Где через <tex> a_{k_i} </tex> обозначается то число, в которое при подстановке <tex> A </tex> переходит число <tex> q_i </tex>.
{{Определение
|definition=
'''Группой подстановок''' (англ. ''group of substitutions'') называется некоторая совокупность подстановок, замкнутая относительно композиции отображений, определяющей бинарную операцию для подстановок на одном и том же множестве.
}}
==См. также==
*[[Теорема Кэли]]
*[[Действие перестановки на набор из элементов, представление в виде циклов]]
==Источники информации==
* [https://en.wikipedia.org/wiki/Involution_(mathematics) Wikipedia {{---}} Involution]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
