Изменения

==Умножение перестановок==

'''Умножением ''' (англ. ''multiplication'') или '''композицией''' (англ. ''composition'') перестановок , представленных в виде целочисленных функций <tex> a_i </tex>, где <tex>i - </tex> позиция элемента, а <tex> a_i </tex> — его номер, называется перестановка, получающаяся получаемая по следующему правилу:

<tex> (a \circ bab)_i = a_{b_i} </tex>

<tex> (a \circ (b \circ cbc))_i = ((a \circ bab) \circ c)_i </tex>

# <tex> (a \circ (b \circ cbc))_i = a_{(b \circ cbc)_i} = a_{b_{c_i}} </tex># <tex> ((a \circ bab) \circ c)_i = (a \circ bab)_{c_i} = a_{b_{c_i}} </tex>

<tex> \varphi(1)=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 5 & 6 & 3 & 1 & 1 \end{pmatrix} </tex> <tex> \varphi(2)=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 1 & 3 & 6 & 5 & 2 \end{pmatrix} </tex>=Пример===

<tex> (\varphi(1) \circ \varphi(2))_ia =</tex><tex> \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & , 5 & , 6 & , 3 & 1 & 4 \end{pmatrix} \circ</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} \circ\begin{pmatrix} 1 & 2 & )(3 & 4 & 5 & , 6 \\ , 4 & 1 & 3 & 6 & 5 & 2 \end{pmatrix} =</tex><tex>\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 2 & 6 & 4 & 1 & 5 \end{pmatrix}) </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}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>

Обратной перестановкой <tex> a^}} {{-1} </tex> к перестановке <tex> a </tex> называется такая перестановка, что:Определение|definition=

Перестановка, содержащая чётное количество инверсий, называется '''чётной''' (англ. ''even permutation''), в противном случае <tex> (a^{-1} \circ a)_i = (a \circ a^{-1})_i = i </tex>'''нечётной''' (англ. ''odd permutation'').

<tex> a_i = a^{-1}_i \Rightarrow Перестановка, меняющая местами только два элемента, называется '''транспозицией''' (a \circ a ^{-1}англ. ''transposition'')_i = (a \circ a)_i = a_{a_i} = i </tex>.

{{Лемма|id=lemma1|statement=Получение обратной перестановки== Если в перестановке, длина которой больше <tex>1</tex>, поменять местами <tex> 2 </tex> элемента, то её четность изменится.

Для элементов, стоящих рядом, истинность утверждения очевидна: их взаимное расположение относительно других элементов не изменилось, а транспозиция этих чисел изменяет количество инверсий на единицу. Пусть теперь между перемещаемыми элементами <tex> a </tex> и <tex> b </tex> находятся <tex> d </tex> элементов, то есть перестановка имеет вид: <tex> \ldots </tex> , <tex> for(i = 0; i a, s_1, s_2, \ldots, s_d, b, \ldots < n; i++)/tex>. Сначала поменяем последовательно { for(j = 0; j < n; j++) { if(p[j] == i + tex> a </tex> с числами <tex> s_1, s_2, \ldots, s_d, b </tex>, а затем число <tex>b</tex> с рядом стоящими <tex> s_d, s_d-1) { op[i] = j , \ldots, s_1 </tex>. В итоге мы выполним <tex> 2\cdot d + 1; }</tex> транспозиций рядом стоящих элементов, то есть чётность перестановки изменится. } }

При представлении ===Получение обратной перестановки в виде циклов обратную перестановку можно легко получить, инвертировав все ребра в циклах.===

Пусть в массиве <tex> a = (1p </tex> содержится перестановка, 3длины <tex> n </tex>, 2)тогда после выполнения алгоритма в массиве <tex> rep </tex> будет содержаться перестановка, обратная ей. '''fun''' reversePerm(4p : '''int[]''', 5rep : '''int[]''') \Rightarrow a^{- '''for''' i = 1} '''to''' n rep[p[i]] = (1, 2, 3), (4, 5) </tex>i;

==Группа перестановок==

'''Группой ''' (англ. ''group'') называется множество <tex> M </tex> с заданной на нём бинарной операцией <tex> \circ: МM\times M \longrightarrow M</tex>, удовлетворяющей следующим свойствам:

Множество перестановок с <tex> n </tex> элементами с операцией умножения является группой (часто группу перестановок называют '''симметрической''' (англ. ''symmetric group''), и обозначают <tex> S_n </tex>).

Свойства <tex>1 </tex> и <tex>3 </tex> (ассоциативность умножения и существование обратной перестановки для любой из перестановок) доказаны выше, а в качестве нейтрального элемента выступает тождественная перестановка (<tex> \pi_i = i </tex>).

==Группа чётных перестановок== {{Определение|definition='''Группа чётных перестановок''' (англ. ''alternating group'') <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> натуральных чисел на себя.  }} Всякая подстановка <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'') называется некоторая совокупность подстановок, замкнутая относительно композиции отображений, определяющей бинарную операцию для подстановок на одном и том же множестве. }} ==См. также==*[[Теорема Кэли]]*[[Действие перестановки на набор из элементов, представление в виде циклов]] ==Источники и литератураинформации==* [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){{---}} Involution]* Н. И. Яцкин, Алгебра Теоремы и алгоритмы, Издательство «Ивановский государственный университет», 2006 г., стр. 161