Изменения

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

'''Умножением ''' (англ. ''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>

# <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)=\begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 5 & 6 & 3 & 1 & 1 \end{bmatrix} </tex> <tex> \varphi(2)=\begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 1 & 3 & 6 & 5 & 2 \end{bmatrix} </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> ==Обратная перестановка==

'''Обратной перестановкой ''' (англ. ''inverse permutation'') <tex> a^{-1} </tex> к перестановке <tex> a </tex> называется такая перестановка, что:

<tex> (a^{-1} \circ a)_i = (a \circ aaa^{-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>

Пусть в массиве p[i] содержится перестановка{{Определение|id = def_involution|definition=Перестановка, тогда в массиве op[i]равная своей обратной, после выполнения алгоритма, будет содержаться обратная перестановканазывается '''инволюцией''' (англ.''involution''):

for(i <tex> a_i = 0; i < n; i++) a^{ for-1}_i \Rightarrow (j aa ^{-1})_i = 0; j < n; j++(aa) _i = a_{ if(p[j] =a_i} = i + 1) { op[i] = j + 1; } } }</tex>, то есть её представление в виде циклов не содержит цикла, размер которого больше двух.

{{Утверждение|statement=Количество инволюционных перестановок длины <tex> a n\geqslant 2 </tex> может быть получено по формуле: <tex> I(n) = I(n-1)+(n-1)\cdot I(n-2) </tex>, 3где <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> инволюций, 2при <tex>a_n = n </tex> (у которых последний элемент представляет собой цикл длины <tex> 1 </tex>), а число инволюций длины <tex> n </tex>, содержащих в своём представлении в виде циклов цикл <tex>(4j, 5n) </tex>, где <tex> 1\leqslant j\Rightarrow a^{leqslant n-1} = </tex>, <tex> (n-1, )\cdot I(n-2)</tex> (так как при фиксированных <tex> j </tex> и <tex> n </tex> имеем <tex> I(n-2) </tex> перестановок оставшихся элементов, 3которые не нарушают свойств инволюции). Таким образом, <tex> I(n) = I(n-1)+(n-1)\cdot I(4, 5n-2) . </tex>

Тогда группой Перестановка, содержащая чётное количество инверсий, называется алгебраическая структура'''чётной''' (англ. ''even permutation''), удовлетворяющая следующим свойствам:в противном случае <tex> - </tex> '''нечётной''' (англ. ''odd permutation'').

}} {{Определение|definition= Перестановка, меняющая местами только два элемента, называется '''транспозицией''' (англ. ''transposition'').  }} {{Лемма|id=lemma1|statement= Если в перестановке, длина которой больше <tex>1</tex>, поменять местами <tex> 2 </tex> элемента, то её четность изменится. |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 </tex> содержится перестановка, длины <tex> n </tex>, тогда после выполнения алгоритма в массиве <tex> rep </tex> будет содержаться перестановка, обратная ей. '''fun''' reversePerm(p : '''int[]''', rep : '''int[]''') '''for''' i = 1 '''to''' n rep[p[i]] = i; ==Группа перестановок== {{Определение|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> - — ассоциативность соответствующей бинарной операции.

# Существование обратного элемента <tex> g^{-1} </tex>, такого, что для Для любого <tex> g \in M </tex>существует <tex> g^{-1} \in M</tex> называемый обратным элементом, такой, что <tex>: g \circ g^{-1} = g^{-1} \circ g = e </tex>

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

Свойства <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=Количество чётных перестановок длины <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