15
правок
Изменения
Как-то так оформил тикет
{{Определение
|definition=
'''Умножением ''' (композицией) перестановок ,представленных в виде целочисленных функций <tex> a_i </tex>, где <tex>i - </tex> позиция элемента, а <tex> a_i </tex> — его номер, называется перестановка, получающаяся получаемая по следующему правилу:
<tex> (ab)_i = a_{b_i} </tex>
===Пример===
<tex> \varphi(1)a =\begin{pmatrix} 1 & 2 & 3 & 4 & , 5 & , 6 \\ 2 & 5 & 6 & , 3 & , 1 & , 4 \end{pmatrix} = (1,2,5)(3,6,4) </tex> <tex> \varphi(2)=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 1 & 3 & 6 & 5 & 2 \end{pmatrix} = (1,4,6,2)(3)(5)</tex>
<tex> (\varphi(1)\varphi(2))_ib =</tex><tex> \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 5 & 6 & 3 & 1 & 4 \end{pmatrix}</tex> <tex> \begin{pmatrix} , 1 & 2 & , 3 & 4 & 5 & , 6 \\ 4 & 1 & 3 & 6 & , 5 & , 2 \end{pmatrix} = \begin{pmatrix} 4 & (1 & 3 & 6 & 5 & 2 \\ 3 & 2 & 6 & , 4 & 1 & 5 \end{pmatrix}\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 1 & 3 & , 6 & , 5 & 2 \end{pmatrix} =) </tex> <tex>\beginab = {pmatrixa_4, a_1, a_3, a_6, a_5, a_2} 1 & 2 & = {3 & 4 & 5 & 6 \\ 3 & , 2 & , 6 & , 4 & , 1 & , 5 \end{pmatrix}</tex>
или
<tex> (\varphi(1)\varphi(2))_iab = (1,2,5)(3,6,4)(1,4,6,25) =(1,3,6,5)(2)(4) = (1,3,6,5) </tex>
==Обратная перестановка==
|definition=
'''Обратной ''' перестановкой <tex> a^{-1} </tex> к перестановке <tex> a </tex> называется такая перестановка, что:
<tex> (a^{-1}a)_i = (aa^{-1})_i = i </tex>
|id = def_involution
|definition=
Перестановка, равная своей обратной, называется '''инволюцией''' (англ. involution): <tex> a_i = a^{-1}_i \Rightarrow (aa ^{-1})_i = (aa)_i = a_{a_i} = i </tex>, то есть её представление в виде циклов не содержит цикла, размер которого больше двух. }}
{{Утверждение|statement=Количество инволюционных перестановок длины <tex> a_i n\geqslant 2 </tex> может быть получено по формуле: <tex> I(n) = a^{I(n-1)+(n-1}_i )\Rightarrow cdot I(aa ^{n-2) </tex>, где <tex> I(0) = I(1})_i = 1. </tex>|proof=Существует <tex> I(aan-1)_i </tex> инволюций, при <tex>a_n = a_{a_i} n </tex>. Число инволюций, содержащих цикл <tex>(j,n)</tex>, где <tex> 1\leq j\leq n-1 </tex>, <tex> (n-1)\cdot I(n-2)</tex>. Имеем, что <tex> I(n) = i I(n-1)+(n-1)\cdot I(n-2). </tex>
}}
{{Определение
|definition=
Перестановка, содержащая чётное количество инверсий, называется '''чётной''', в противном случае <tex> - </tex> '''нечётной'''.
}}
{{Определение
|definition=
Перестановка, меняющая местами только два элемента, называется '''транспозицией''' (англ. transposition).
}}
{{Лемма|id=lemma1
|statement=
Если в перестановке, длина которой больше <tex>1</tex>, поменять местами <tex> 2 </tex> элемента, то её четность изменится.
|proof=
Для элементов, стоящих рядом, истинность утверждения очевидна: их взаимное расположение относительно других элементов не изменилось, а транспозиция этих чисел изменяет количество инверсий на единицу. Пусть теперь между перемещаемыми элементами <tex> a </tex> и <tex> b </tex> находятся <tex> d </tex> элементов, то есть перестановка имеет вид: <tex> ..., a, s_1, s_2, ..., s_d, b, ... </tex>. Сначала поменяем последовательно <tex> a </tex> с числами <tex> s_1, s_2, ..., s_d, b </tex>, а затем число <tex>b</tex> с рядом стоящими <tex> s_d, s_d-1, ..., s_1 </tex>. В итоге мы выполним <tex> 2\cdot d + 1 </tex> транспозиций рядом стоящих элементов, то есть чётность перестановки изменится.
}}
for(i = 0; i < n; i++)
При представлении перестановки в виде циклов обратную перестановку можно легко получить, инвертировав все ребра в циклах.
boolean[] visited = new boolean[n];
for (int i = 0; i < n; ++i)
==Группа перестановок==
{{Определение
|definition=
'''Группой ''' называется множество <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> — ассоциативность соответствующей бинарной операции.
[[Теорема Кэли]] утверждает, что любая конечная группа изоморфна подгруппе некоторой группе перестановок.
==Группа чётных перестановок==
{{Определение
|definition=
'''Группа чётных перестановок''' <tex> A_n </tex> является подгруппой симметричной группы перестановок, образованной всеми чётными перестановками. Композиция не выводит из группы, так как если представить каждую перестановку группы в виде чётного числа транспозиций и перемножить их, чётность не изменится.
}}
{{Утверждение
|statement=
Количество чётных перестановок длины <tex> n </tex> равно количеству нечётных и равно <tex> \dfrac{n!}{2} </tex>
|proof=
Пусть число число чётных перестановок <tex> - </tex> <tex> a</tex>, а нечётных <tex> - </tex> <tex> b </tex>. Сделаем транспозицию <tex> (1, 2) </tex> для всех чётных перестановок. Получим <tex> a </tex> нечётных различных перестановок, то есть <tex> a\leqslant b </tex>. Проделаем то же самое с нечётными перестановками. Получим, что <tex> b\leqslant a </tex>, то есть <tex> a = b </tex> и <tex> a = \dfrac{n!}{2} </tex>.
}}
==Подстановка==
{{Определение
|definition=
'''Подстановкой''' (англ. substitution) называется всякое взаимно однозначное отображение <tex> A </tex> множества первых <tex>n</tex> натуральных чисел на себя.
}}
Всякая подстановка A может быть записана при помощи двух перестановок, подписанных одна под другой:
<tex> A = \begin{pmatrix} q_1 & q_2 & ... & q_n \\ a_{k_1} & a_{k_2} & ... & a_{k_n} \end{pmatrix} </tex>
Где через <tex> a_{k_i} </tex> обозначается то число, в которое при подстановке <tex> A </tex> переходит число <tex> q_i </tex>.
==Источники и литература==
* [httphttps://ruen.wikipedia.org/wiki/%D0%98%D0%BD%D0%B2%D0%BE%D0%BB%D1%8E%D1%86%D0%B8%D1%8F_Involution_(%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0mathematics) инволюция (Wikipedia, the free encyclopedia)]
* Н. И. Яцкин, Алгебра Теоремы и алгоритмы, Издательство «Ивановский государственный университет», 2006 г., стр. 161
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
