Изменения
→Умножение перестановок
==Умножение перестановок==
{{Определение
|definition=
'''Умножением ''' (англ. ''multiplication'') или '''композицией''' (англ. ''composition'') перестановок , представленных в виде целочисленных функций <tex> a_i </tex>, где <tex>i - </tex> позиция элемента, а <tex> a_i </tex> — его номер, называется перестановка, получающаяся получаемая по следующему правилу:
<tex> (a \circ bab)_i = a_b_{b_ia_i} </tex>
}}
Умножение перестановок ассоциативно:
<tex> (a \circ (b \circ cbc))_i = ((a \circ bab) \circ c)_i </tex>
|proof=
Доказывается простым раскрытием скобок.
# <tex> (a \circ (b \circ cbc))_i = a_{(b \circ cbc)_i_{a_i} = a_c_{b_{c_ia_i}} </tex># <tex> ((a \circ bab) \circ c)_i = c_{(a \circ bab)_{c_i_i} = a_c_{b_{c_ia_i}} </tex>
}}
<tex> (\varphi(1) \circ \varphi(2))_ia =</tex><tex> \begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & , 5 & , 6 & , 3 & 1 & 4 \end{bmatrix} \circ</tex> <tex> \begin{bmatrix} , 1 & 2 & 3 & 4 & 5 & 6 \\ , 4 & 1 & 3 & 6 & 5 & 2 \end{bmatrix} = \begin{bmatrix} 4 & (1 & 3 & 6 & 5 & , 2 \\ 3 & 2 & 6 & 4 & 1 & , 5 \end{bmatrix} \circ\begin{bmatrix} 1 & 2 & )(3 & 4 & 5 & , 6 \\ , 4 & 1 & 3 & 6 & 5 & 2 \end{bmatrix} =</tex><tex>\begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 2 & 6 & 4 & 1 & 5 \end{bmatrix}) </tex>
<tex> b = {4, 1, 3, 6, 5, 2} = (1, 4, 6, 2) </tex> <tex> ab = {a_4, a_1, a_3, a_6, a_5, a_2} = {3, 2, 6, 4, 1, 5} </tex> или <tex> ab = (1, 2, 5)(3, 6, 4)(1, 4, 6, 5) = (1, 3, 6, 5)(2)(4) = (1, 3, 6, 5) </tex> ==Обратная перестановка==
{{Определение
|definition=
'''Обратной перестановкой ''' (англ. ''inverse permutation'') <tex> a^{-1} </tex> к перестановке <tex> a </tex> называется такая перестановка, что:
<tex> (a^{-1} \circ a)_i = (a \circ aaa^{-1})_i = i </tex>
}}
}} Также обратная перестановка единственна. Это следует из того, что для каждой <tex> i </tex>-ой позиций в исходной перестановке однозначно определяется <tex> j </tex> a = (1, 3, 2), (4, 5) \Rightarrow a^{-1} = (1ая позиций в обратной перестановке, 2, 3), (4, 5) значение которой есть <tex> i </tex>
{{Определение
|id = def_involution
|definition=
Перестановка, равная своей обратной, называется '''инволюцией''' (англ. ''involution''):
<tex> a_i = a^{-1}_i \Rightarrow (a \circ a aa ^{-1})_i = (a \circ aaa)_i = a_{a_i} = i </tex>, то есть её представление в виде циклов не содержит цикла, размер которого больше двух.
}}
{{Утверждение
|statement=
|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\leqslant j\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''). }} {{Лемма|id=lemma1|statement= Если в перестановке, длина которой больше <tex>1</tex>, поменять местами <tex> 2 </tex> элемента, то её четность изменится.
}}
===Получение обратной перестановки=== Пусть в массиве <tex> p </tex> содержится перестановка, длины <tex> n </tex>, тогда после выполнения алгоритма в массиве <tex> rep </tex> будет содержаться перестановка, обратная ей. '''fun''' reversePerm(p : '''int[]''', rep : '''int[]''') '''for''' i = 1 '''to''' n rep[p[i]] = i; ==Группа перестановок==
{{Определение
|definition=
{{Утверждение
|statement=
Множество перестановок с <tex> n </tex> элементами с операцией умножения является группой (часто группу перестановок называют '''симметрической''' (англ. ''symmetric group''), и обозначают <tex> S_n </tex>).
|proof=
Свойства <tex>1</tex> и <tex>3</tex> (ассоциативность умножения и существование обратной перестановки для любой из перестановок) доказаны выше, а в качестве нейтрального элемента выступает тождественная перестановка (<tex> \pi_i = i </tex>).
}}
Мощность симметрической группы: <tex>\left\vert S_n \right\vert = n!</tex>
[[Теорема Кэли]] утверждает, что любая конечная группа изоморфна подгруппе некоторой группе перестановок.
==Группа чётных перестановок==
{{Определение
|definition=
'''Группа чётных перестановок''' (англ. ''alternating group'') <tex> A_n </tex> является подгруппой симметричной группы перестановок, образованной всеми чётными перестановками. Композиция не выводит из группы, так как если представить каждую перестановку группы в виде чётного числа транспозиций и перемножить их, чётность не изменится.
}}
{{Утверждение
|statement=
|proof=
}}
==Источники информации==* [[Теорема Кэлиhttps://en.wikipedia.org/wiki/Involution_(mathematics) Wikipedia {{---}} Involution]] утверждает, что любая конечная группа изоморфна подгруппе соответствующей группе перестановок.
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]