Умножение перестановок, обратная перестановка, группа перестановок — различия между версиями
Denis (обсуждение | вклад) |
м (rollbackEdits.php mass rollback) |
||
(не показано 15 промежуточных версий 5 участников) | |||
Строка 3: | Строка 3: | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
− | '''Умножением''' (англ. ''multiplication'') или '''композицией''' (англ. ''composition'') перестановок,представленных в виде целочисленных функций <tex> a_i </tex>, где <tex>i - </tex> позиция элемента, а <tex> a_i </tex> — его номер, называется перестановка, получаемая по следующему правилу: | + | '''Умножением''' (англ. ''multiplication'') или '''композицией''' (англ. ''composition'') перестановок, представленных в виде целочисленных функций <tex> a_i </tex>, где <tex>i - </tex> позиция элемента, а <tex> a_i </tex> — его номер, называется перестановка, получаемая по следующему правилу: |
− | <tex> (ab)_i = | + | <tex> (ab)_i = b_{a_i} </tex> |
}} | }} | ||
Строка 19: | Строка 19: | ||
Доказывается простым раскрытием скобок. | Доказывается простым раскрытием скобок. | ||
− | # <tex> (a(bc))_i = | + | # <tex> (a(bc))_i = (bc)_{a_i} = c_{b_{a_i}} </tex> |
− | # <tex> ((ab)c)_i = (ab) | + | # <tex> ((ab)c)_i = c_{(ab)_i} = c_{b_{a_i}} </tex> |
}} | }} | ||
+ | |||
+ | Перед прочтением примера перемножения перестановок рекомендуем познакомиться с циклами в данной статье: [[Действие перестановки на набор из элементов, представление в виде циклов]] | ||
===Пример=== | ===Пример=== | ||
Строка 28: | Строка 30: | ||
<tex> a = {2, 5, 6, 3, 1, 4} = (1, 2, 5)(3, 6, 4) </tex> | <tex> a = {2, 5, 6, 3, 1, 4} = (1, 2, 5)(3, 6, 4) </tex> | ||
− | <tex> b = {4, 1, 3, 6, 5, 2} = (1, 4, 6, | + | <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 = {a_4, a_1, a_3, a_6, a_5, a_2} = {3, 2, 6, 4, 1, 5} </tex> | ||
Строка 41: | Строка 43: | ||
|definition= | |definition= | ||
− | '''Обратной перестановкой''' (англ. '' | + | '''Обратной перестановкой''' (англ. ''inverse permutation'') <tex> a^{-1} </tex> к перестановке <tex> a </tex> называется такая перестановка, что: |
<tex> (a^{-1}a)_i = (aa^{-1})_i = i </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> | ||
{{Определение | {{Определение | ||
Строка 60: | Строка 72: | ||
Количество инволюционных перестановок длины <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> | Количество инволюционных перестановок длины <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= | |proof= | ||
− | Существует <tex> I(n-1)</tex> инволюций, при <tex>a_n = n </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\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> |
}} | }} | ||
Строка 67: | Строка 79: | ||
|definition= | |definition= | ||
− | Перестановка, содержащая чётное количество инверсий, называется '''чётной''', в противном случае <tex> - </tex> '''нечётной'''. | + | Перестановка, содержащая чётное количество инверсий, называется '''чётной''' (англ. ''even permutation''), в противном случае <tex> - </tex> '''нечётной''' (англ. ''odd permutation''). |
}} | }} | ||
Строка 90: | Строка 102: | ||
===Получение обратной перестановки=== | ===Получение обратной перестановки=== | ||
− | Пусть в массиве <tex>p | + | Пусть в массиве <tex> p </tex> содержится перестановка, длины <tex> n </tex>, тогда после выполнения алгоритма в массиве <tex> rep </tex> будет содержаться перестановка, обратная ей. |
'''fun''' reversePerm(p : '''int[]''', rep : '''int[]''') | '''fun''' reversePerm(p : '''int[]''', rep : '''int[]''') | ||
− | + | '''for''' i = 1 '''to''' n | |
− | + | rep[p[i]] = i; | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
==Группа перестановок== | ==Группа перестановок== | ||
Строка 134: | Строка 121: | ||
{{Утверждение | {{Утверждение | ||
|statement= | |statement= | ||
− | Множество перестановок с <tex> n </tex> элементами с операцией умножения является группой (часто группу перестановок называют симметрической (англ. ''symmetric group''), и обозначают <tex> S_n </tex>). | + | Множество перестановок с <tex> n </tex> элементами с операцией умножения является группой (часто группу перестановок называют '''симметрической''' (англ. ''symmetric group''), и обозначают <tex> S_n </tex>). |
|proof= | |proof= | ||
− | Свойства <tex>1</tex> и <tex>3</tex> доказаны выше, а в качестве нейтрального элемента выступает тождественная перестановка (<tex> \pi_i = i </tex>). | + | Свойства <tex>1</tex> и <tex>3</tex> (ассоциативность умножения и существование обратной перестановки для любой из перестановок) доказаны выше, а в качестве нейтрального элемента выступает тождественная перестановка (<tex> \pi_i = i </tex>). |
}} | }} | ||
Строка 147: | Строка 134: | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
− | '''Группа чётных перестановок''' (англ. ''alternating group'')<tex> A_n </tex> является подгруппой симметричной группы перестановок, образованной всеми чётными перестановками. Композиция не выводит из группы, так как если представить каждую перестановку группы в виде чётного числа транспозиций и перемножить их, чётность не изменится. | + | '''Группа чётных перестановок''' (англ. ''alternating group'') <tex> A_n </tex> является подгруппой симметричной группы перестановок, образованной всеми чётными перестановками. Композиция не выводит из группы, так как если представить каждую перестановку группы в виде чётного числа транспозиций и перемножить их, чётность не изменится. |
}} | }} | ||
Строка 177: | Строка 164: | ||
}} | }} | ||
+ | ==См. также== | ||
+ | *[[Теорема Кэли]] | ||
+ | *[[Действие перестановки на набор из элементов, представление в виде циклов]] | ||
+ | ==Источники информации== | ||
+ | * [https://en.wikipedia.org/wiki/Involution_(mathematics) Wikipedia {{---}} Involution] | ||
− | |||
− | |||
− | |||
[[Категория: Дискретная математика и алгоритмы]] | [[Категория: Дискретная математика и алгоритмы]] | ||
[[Категория: Комбинаторика]] | [[Категория: Комбинаторика]] |
Текущая версия на 19:28, 4 сентября 2022
Содержание
Умножение перестановок
Определение: |
Умножением (англ. multiplication) или композицией (англ. composition) перестановок, представленных в виде целочисленных функций | , где позиция элемента, а — его номер, называется перестановка, получаемая по следующему правилу:
Утверждение: |
Умножение перестановок ассоциативно:
|
Доказывается простым раскрытием скобок. |
Перед прочтением примера перемножения перестановок рекомендуем познакомиться с циклами в данной статье: Действие перестановки на набор из элементов, представление в виде циклов
Пример
или
Обратная перестановка
Определение: |
Обратной перестановкой (англ. inverse permutation) | к перестановке называется такая перестановка, что:
Утверждение: |
Для каждой перестановки существует перестановка, обратная ей. |
Пусть дана перестановка | , построим обратную ей перестановку : если , то . Очевидно, что данная перестановка является обратной к .
Также обратная перестановка единственна. Это следует из того, что для каждой
-ой позиций в исходной перестановке однозначно определяется -ая позиций в обратной перестановке, значение которой есть
Определение: |
Перестановка, равная своей обратной, называется инволюцией (англ. involution): | , то есть её представление в виде циклов не содержит цикла, размер которого больше двух.
Утверждение: |
Количество инволюционных перестановок длины может быть получено по формуле: , где |
Докажем формулу по индукции. Базой являются | . Предположим, что для всех , где , , формула верна. Рассмотрим перестановку длины и попробуем найти количество инволюций этой длины. Существует инволюций, при (у которых последний элемент представляет собой цикл длины ), а число инволюций длины , содержащих в своём представлении в виде циклов цикл , где , (так как при фиксированных и имеем перестановок оставшихся элементов, которые не нарушают свойств инволюции). Таким образом,
Определение: |
Перестановка, содержащая чётное количество инверсий, называется чётной (англ. even permutation), в противном случае | нечётной (англ. odd permutation).
Определение: |
Перестановка, меняющая местами только два элемента, называется транспозицией (англ. transposition). |
Лемма: |
Если в перестановке, длина которой больше , поменять местами элемента, то её четность изменится. |
Доказательство: |
Для элементов, стоящих рядом, истинность утверждения очевидна: их взаимное расположение относительно других элементов не изменилось, а транспозиция этих чисел изменяет количество инверсий на единицу. Пусть теперь между перемещаемыми элементами | и находятся элементов, то есть перестановка имеет вид: , . Сначала поменяем последовательно с числами , а затем число с рядом стоящими . В итоге мы выполним транспозиций рядом стоящих элементов, то есть чётность перестановки изменится.
Получение обратной перестановки
Пусть в массиве
содержится перестановка, длины , тогда после выполнения алгоритма в массиве будет содержаться перестановка, обратная ей.fun reversePerm(p : int[], rep : int[]) for i = 1 to n rep[p[i]] = i;
Группа перестановок
Определение: |
Группой (англ. group) называется множество
| с заданной на нём бинарной операцией , удовлетворяющей следующим свойствам:
Утверждение: |
Множество перестановок с элементами с операцией умножения является группой (часто группу перестановок называют симметрической (англ. symmetric group), и обозначают ). |
Свойства | и (ассоциативность умножения и существование обратной перестановки для любой из перестановок) доказаны выше, а в качестве нейтрального элемента выступает тождественная перестановка ( ).
Мощность симметрической группы:
Теорема Кэли утверждает, что любая конечная группа изоморфна подгруппе некоторой группе перестановок.
Группа чётных перестановок
Определение: |
Группа чётных перестановок (англ. alternating group) | является подгруппой симметричной группы перестановок, образованной всеми чётными перестановками. Композиция не выводит из группы, так как если представить каждую перестановку группы в виде чётного числа транспозиций и перемножить их, чётность не изменится.
Утверждение: |
Количество чётных перестановок длины равно количеству нечётных и равно |
Пусть число число чётных перестановок | , а нечётных . Сделаем транспозицию для всех чётных перестановок. Получим нечётных различных перестановок, то есть . Проделаем то же самое с нечётными перестановками. Получим, что , то есть и .
Группа подстановок
Определение: |
Подстановкой (англ. substitution) называется всякое взаимно однозначное отображение | множества первых натуральных чисел на себя.
Всякая подстановка может быть записана при помощи двух перестановок, подписанных одна под другой:
Где через
обозначается то число, в которое при подстановке переходит число .
Определение: |
Группой подстановок (англ. group of substitutions) называется некоторая совокупность подстановок, замкнутая относительно композиции отображений, определяющей бинарную операцию для подстановок на одном и том же множестве. |