47
правок
Изменения
м
Циклы подробно рассматриваются здесь: [[Действие перестановки на набор из элементов, представление в виде циклов]]
Очевидно, что Докажем формулу по '''индукции'''. '''Базой''' являются <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>
'''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;
→Умножение перестановок: delete "обратная формулировка" - не нашел подтверждений
{{Определение
|definition=
'''Умножением''' (англ. ''multiplication'') или '''композицией''' (англ. ''composition'') перестановок,представленных в виде целочисленных функций <tex> a_i </tex>, где <tex>i - </tex> позиция элемента, а <tex> a_i </tex> — его номер, называется перестановка, получаемая по следующему правилу:
<tex> (ab)_i = a_{b_i} </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=
'''Обратной перестановкой''' (англ. ''an 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>n\geqslant 2 </tex> может быть получено по формуле: <tex> I(n) = I(n-1)+(n-1)\cdot I(n-2) </tex>, где <tex> I(0) = I(1) = 1. </tex>
|proof=
}}
===Получение обратной перестановки===
Пусть в массиве <tex>p[i]</tex> содержится перестановка, длины <tex> n </tex>, тогда после выполнения алгоритма в массиве <tex>rep[i]</tex>, после выполнения алгоритма, будет содержаться перестановка, обратная перестановкаей.
'''fun''' reversePerm(p : '''int[]''', rep : '''int[]''')
==Группа перестановок==
*[[Действие перестановки на набор из элементов, представление в виде циклов]]
==Источники и литератураинформации==* [https://en.wikipedia.org/wiki/Involution_(mathematics)Wikipedia {{---}} Involution]* Н. И. Яцкин, Алгебра Теоремы и алгоритмы, Издательство «Ивановский государственный университет», 2006 г., стр. 161
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
