Изменения

'''Умножением''' (англ. ''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> b = {4, 1, 3, 6, 5, 2} = (1, 4, 6, 52) </tex>

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

Докажем формулу по '''индукции'''. '''Базой''' являются <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>

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

Пусть в массиве <tex>p[i]</tex> содержится перестановка, длины <tex> n </tex>, тогда после выполнения алгоритма в массиве <tex>rep[i]</tex>, после выполнения алгоритма, будет содержаться перестановка, обратная перестановкаей.

'''int''' n = p.size; '''for''' i = 0 1 '''to''' n '''for''' j = 0 '''to''' n '''if''' p[j] == i + 1 rep[i] = j + 1; При представлении перестановки в виде циклов обратную перестановку можно легко получить, инвертировав все ребра в циклах. <tex> a = (1, 3, 2), (4, 5) \Rightarrow a^{-1} = (1, 2, 3), (4, 5) </tex> Отсюда следует более эффективный алгоритм, где <tex> visited[] </tex> - массив посещённых элементов: '''fun''' reversePerm (visited : '''boolean[]''', p : '''int[]''', rep : '''int[]''') '''int''' n = p.size; '''for''' i = 0 '''to''' n '''if''' visited[i] '''continue'''; ''<font color="green">// инвертировать цикл, начинающийся в позиции <tex> i </tex> </font>'' '''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;

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

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

'''Группа чётных перестановок''' (англ. ''alternating group'')<tex> A_n </tex> является подгруппой симметричной группы перестановок, образованной всеми чётными перестановками. Композиция не выводит из группы, так как если представить каждую перестановку группы в виде чётного числа транспозиций и перемножить их, чётность не изменится.