Умножение перестановок, обратная перестановка, группа перестановок
Также обратная перестановка единственна. Это следует из того, что для каждой [math] i [/math] -ой позиций в исходной перестановке однозначно определяется [math] j [/math] -ая позиций в обратной перестановке, значение которой есть [math] i [/math]
| Определение: |
| Перестановка, равная своей обратной, называется инволюцией (англ. involution): [math] a_i = a^_i \Rightarrow (aa ^)_i = (aa)_i = a_ = i [/math] , то есть её представление в виде циклов не содержит цикла, размер которого больше двух. |
Количество инволюционных перестановок длины [math]n\geqslant 2 [/math] может быть получено по формуле: [math] I(n) = I(n-1)+(n-1)\cdot I(n-2) [/math] , где [math] I(0) = I(1) = 1. [/math]
| Определение: |
| Перестановка, содержащая чётное количество инверсий, называется чётной (англ. even permutation), в противном случае [math] — [/math] нечётной (англ. odd permutation). |
| Определение: |
| Перестановка, меняющая местами только два элемента, называется транспозицией (англ. transposition). |
Если в перестановке, длина которой больше [math]1[/math] , поменять местами [math] 2 [/math] элемента, то её четность изменится.
Получение обратной перестановки
Пусть в массиве [math] p [/math] содержится перестановка, длины [math] n [/math] , тогда после выполнения алгоритма в массиве [math] rep [/math] будет содержаться перестановка, обратная ей.
fun reversePerm(p : int[], rep : int[]) for i = 1 to n rep[p[i]] = i;
Группа перестановок
Множество перестановок с [math] n [/math] элементами с операцией умножения является группой (часто группу перестановок называют симметрической (англ. symmetric group), и обозначают [math] S_n [/math] ).
Мощность симметрической группы: [math]\left\vert S_n \right\vert = n![/math]
Теорема Кэли утверждает, что любая конечная группа изоморфна подгруппе некоторой группе перестановок.
Группа чётных перестановок
| Определение: |
| Группа чётных перестановок (англ. alternating group) [math] A_n [/math] является подгруппой симметричной группы перестановок, образованной всеми чётными перестановками. Композиция не выводит из группы, так как если представить каждую перестановку группы в виде чётного числа транспозиций и перемножить их, чётность не изменится. |
Количество чётных перестановок длины [math] n [/math] равно количеству нечётных и равно [math] \dfrac [/math]
Группа подстановок
| Определение: |
| Подстановкой (англ. substitution) называется всякое взаимно однозначное отображение [math] A [/math] множества первых [math]n[/math] натуральных чисел на себя. |
Всякая подстановка [math]A[/math] может быть записана при помощи двух перестановок, подписанных одна под другой:
[math] A = \begin q_1 & q_2 & \ldots & q_n \\ a_ & a_ & \ldots & a_ \end [/math]
Где через [math] a_ [/math] обозначается то число, в которое при подстановке [math] A [/math] переходит число [math] q_i [/math] .
| Определение: |
| Группой подстановок (англ. group of substitutions) называется некоторая совокупность подстановок, замкнутая относительно композиции отображений, определяющей бинарную операцию для подстановок на одном и том же множестве. |
См. также
- Теорема Кэли
- Действие перестановки на набор из элементов, представление в виде циклов
Источники информации
Как перемножать циклы перестановок
Расположение первых n натуральных чисел в порядке их возрастания определяется в качестве эталонного, а любой другой порядок размещения этих чисел — как перестановка «нормального» расположения.
Оказывается, что произвольная перестановка таких чисел может быть получена из нормальной перестановки посредством некоторого числа транспозиций, то есть переменами позиций одной пары элементов перестановки при сохранении позиций остальных элементов.
Под перестановкой множества S понимается множество этих же чисел, упорядоченное некоторым другим образом:
Перестановка называется транспозицией , если переставляются местами только два элемента множества, тогда как остальные элементы остаются на своих местах.
Пример перестановки:
Пример транспозиции:
Любую перестановку множества S можно осуществить посредством нескольких транспозиций. Например, перестановка является результатом трех транспозиций множества S :
Говорят, что перестановка множества S содержит инверсию элементов i j и i k , если нарушен их естественный порядок расположения, т.е. больший элемент расположен левее меньшего:
i j > i k ( j < k ).
Например, перестановка содержит три инверсии элементов:
2 и 1,
4 и 1,
4 и 3.
Число инверсий определяет четность перестановки. Перестановка называется четной, если она содержит четное число инверсий элементов. Нечетная перестановка содержит нечетное число инверсий.
Заметим, что четная перестановка может быть преобразована к естественному порядку посредством только четного числа транспозиций, тогда как для преобразования нечетной перестановки к естественному порядку требуется нечетное число транспозиций. (Это утверждение является следствием Теоремы 1, см раздел «Теоремы о транспозициях и перестановках».)
Научный форум dxdy
Определить четность подстановки:
Будь это транспозиция непересекающихся циклов, я бы легко привела её к виду
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\ x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & x_7 & x_8 \end$» /> и подсчитала количество инверсий.
Но тут транспозиция пересекающихся циклов, поэтому так просто разобраться не получается.
В учебниках, в основном, пишут про то, как обычный вид представить в качестве произведения скобок с двумя элементами, но не наоборот (если кто подскажет хороший ресурс, как сделать транспозицию пересекающихся скобок с количеством элементов в них больше двух, буду благодарна).
Я пыталась склеить по третьей скобке , но в первых скобках помимо этих чисел есть ещё повторяющиеся, которые не дают мне сделать преобразование.
Других подходящих методов больше не нашла.
Прошу направить на путь истинный!
Re: Транспозиция пересекающихся циклов
27.01.2017, 19:27
myltykritik в сообщении #1187801 писал(а):
А что мешает вам также поступить и в этом случае? Я думал, там нужно что-то этакое, а вы согласны на простой подсчет, ну дык и посчитайте, предварительно перемножив.
Re: Транспозиция пересекающихся циклов
27.01.2017, 20:42
Последний раз редактировалось Sonic86 27.01.2017, 20:46, всего редактировалось 3 раз(а).
myltykritik в сообщении #1187801 писал(а):
Вычислять произведение циклов вообще, конечно, надо уметь, но для вычисления четности подстановки саму подстановку можно не вычислять.
http://www.algebraical.info/doku.php?id . 0%BA%D0%B8
Вычислить все произведение можно через вычисление образа элементов 
для каждого 
.
myltykritik в сообщении #1187801 писал(а):
В учебниках, в основном, пишут про то, как обычный вид представить в качестве произведения скобок с двумя элементами, но не наоборот
Ну просто попробуйте обратите процесс да и все. Начните с того, как представить простой цикл 
в обычном виде 
Re: Транспозиция пересекающихся циклов
27.01.2017, 21:42
В целом, не понимаю, как перемножить.
И говоря «перемножить», вы имеете виду: привести к обычному виду?
Типа:
умножить на
и потом на третью скобочку?
И уже у этого посчитать инверсию?
Sinoid в сообщении #1187808 писал(а):
myltykritik в сообщении #1187801 писал(а):
| Заслуженный участник |
Последний раз редактировалось Sonic86 27.01.2017, 22:02, всего редактировалось 1 раз.
myltykritik в сообщении #1187835 писал(а):
И говоря «перемножить», вы имеете виду: привести к обычному виду?
Мне без разницы — к любому виду, лишь бы умножение исчезло.
myltykritik в сообщении #1187835 писал(а):
И уже у этого посчитать инверсию?
Для решения исходной задачи я предлагаю вообще ничего не перемножать, а вычислять инверсию сразу, от произведения: 
( 
— четность перестановки, 
— перестановки)
myltykritik в сообщении #1187835 писал(а):
В целом, не понимаю, как перемножить.
Ну елки, так начните с самого простого.
Перестановки — это биекции на множестве 
, то 
. Например, если 
, то 
, итого 
.
Потом рассмотрите запись перестановки в виде цикла и вытащите оттуда правило умножения перестановок в виде циклов.
Re: Транспозиция пересекающихся циклов
28.01.2017, 03:32
А что такое «транспозиция циклов», хоть пересекающихся, хоть нет? Разве есть такой термин? Что такое «транспозиция»?
Re: Транспозиция пересекающихся циклов
28.01.2017, 09:36
«транспозиция» следует читать «композиция», т.е. последовательное выполнение отображений, известное также как «сложная функция».
Re: Транспозиция пересекающихся циклов
30.01.2017, 16:08
Последний раз редактировалось myltykritik 30.01.2017, 16:14, всего редактировалось 3 раз(а).
vpb , тему разбираю недавно, но, кажется, в учебниках именно так называется перемножение циклов.
Brukvalub , а как это применимо к моему примеру? Не могу понять, как перемножать эти скобочки.
Sonic86 в сообщении #1187839 писал(а):
Перестановки — это биекции на множестве , то . Например, если , то , итого .
Потом рассмотрите запись перестановки в виде цикла и вытащите оттуда правило умножения перестановок в виде циклов.
У вас здесь пример с циклами, которые я умею перемножать.
Но у меня в примере пересекающиеся циклы! И у меня не получается применить ваш совет к ним.
Re: Транспозиция пересекающихся циклов
30.01.2017, 18:06
Последний раз редактировалось Sinoid 30.01.2017, 18:10, всего редактировалось 1 раз.
myltykritik в сообщении #1188609 писал(а):
Но у меня в примере пересекающиеся циклы! И у меня не получается применить ваш совет к ним.
Так это ничего не меняет. Смотрим, ага, в первом множителе 1 переходит в 4, во втором множителе 4 переходит в 8, в третьем множителе 8 вообще ни во что не переходит. Значит, в произведении (конечном) 1 переходит в.
Кстати, а порядок умножения-то слева направо?
Re: Транспозиция пересекающихся циклов
30.01.2017, 18:43
Да, именно так, как Вы писали в посте от 21:42 27.01, и сделайте. Если по Кострикину вдруг непонятно, как обращаются с подстановками, почитайте Куроша «Курс высшей алгебры», самое начало, там еще проще. Или ван дер Варден «Алгебра», начало гл.2.
Re: Транспозиция пересекающихся циклов
30.01.2017, 18:48
myltykritik в сообщении #1188609 писал(а):
У вас здесь пример с циклами, которые я умею перемножать.
Но у меня в примере пересекающиеся циклы! И у меня не получается применить ваш совет к ним.
Пример Sonic86 как раз-таки с пересекающимися циклами 
и 
. А совет просто в том, чтобы проследить, какой элемент в какой переходит по определению композиции перестановок . И даже расписано. В результате было бы интересно знать, что у вас не получается, если вам интересно, чтобы с этим что-то сделали.
Re: Транспозиция пересекающихся циклов
30.01.2017, 19:21
arseniiv в сообщении #1188663 писал(а):
А совет просто в том, чтобы проследить, какой элемент в какой переходит по определению композиции перестановок.
Да тут недопонимание самого
arseniiv в сообщении #1188663 писал(а):
определени я композиции перестановок
Re: Транспозиция пересекающихся циклов
31.01.2017, 12:57
Последний раз редактировалось myltykritik 31.01.2017, 13:04, всего редактировалось 3 раз(а).
Sinoid в сообщении #1188648 писал(а):
Кстати, а порядок умножения-то слева направо?
А вот это вопрос. Уточнять буду, потому что, вроде бы, в каких-то примерах я и справа налево умножала.
vpb в сообщении #1188660 писал(а):
Да, именно так, как Вы писали в посте от 21:42 27.01, и сделайте. Если по Кострикину вдруг непонятно, как обращаются с подстановками, почитайте Куроша «Курс высшей алгебры», самое начало, там еще проще. Или ван дер Варден «Алгебра», начало гл.2.
А вот тут ещё подняли вопрос: порядок умножения же тоже должен быть важен?
Или если я привожу к стандартному виду, то уже нет?
arseniiv в сообщении #1188663 писал(а):
myltykritik в сообщении #1188609 писал(а):
У вас здесь пример с циклами, которые я умею перемножать.
Но у меня в примере пересекающиеся циклы! И у меня не получается применить ваш совет к ним.
Пример Sonic86 как раз-таки с пересекающимися циклами и . А совет просто в том, чтобы проследить, какой элемент в какой переходит по определению композиции перестановок . И даже расписано. В результате было бы интересно знать, что у вас не получается, если вам интересно, чтобы с этим что-то сделали.
Пример, как перемножить 
и 
встречается чуть ли не первым в учебниках, а вот — нет.
Да тут недопонимание самого
arseniiv в сообщении #1188663 писал(а):
определени я композиции перестановок
Re: Транспозиция пересекающихся циклов
31.01.2017, 14:28
myltykritik в сообщении #1188832 писал(а):
а вот — нет
Тут всё совершенно аналогично. Будем пока так же предполагать, что умножение справа налево. Начнём, скажем, с 1: 
. Будем сразу получать циклы результата, потому дальше проверим 4: 
. Дальше: 
. Цикл не хочет заканчиваться, ну что ж: 
; 
; 
; 
. Всё, мы знаем, что результат — это произведение цикла 
и ещё, возможно, каких-то непересекающихся (и с ним, и друг с другом). Здесь видно, что больше никаких, потому что больше никаких точек ни один из циклов в исходном произведении не двигал. Если бы там нашлась, скажем, 5 или 11, мы бы пошли с неё искать следующий цикл, и так до тех пор, пока необработанные точки, встречавшиеся в циклах, не кончатся.
Теперь найдите произведение .
Re: Транспозиция пересекающихся циклов
31.01.2017, 17:46
myltykritik в сообщении #1188832 писал(а):
А вот тут ещё подняли вопрос: порядок умножения же тоже должен быть важен?
Порядок вычисления произведений неважен, потому что умножение подстановок ассоциативно (а оно ассоциативно по очевидной причине).
myltykritik в сообщении #1188832 писал(а):
Пример, как перемножить 
и 
встречается чуть ли не первым в учебниках, а вот — нет.
В этих задачах нет решительно никакой разницы. Ну в крайнем случае можно циклы преобразовать в перестановки и потом их стандартно перемножить.
| Страница 1 из 2 |
[ Сообщений: 16 ] |
На страницу 1 , 2 След. |
Знак перестановки: транспозиции vs инверсии
В этой статье мы обсудим с разных сторон такое важное понятие, как знак перестановки. Перестановки играют важную роль в разных разделах математики, прежде всего в алгебре и комбинаторике. Знак (чётность) перестановки — это её важнейшая характеристика. На ней, в частности, основана теория определителей.
Перестановкой конечного множества называется любое его биективное (т. е. взаимно однозначное) соответствие на себя. Перестановку часто записывают в виде таблицы: в верхней строке — аргументы, в нижней — значения функции. Например,
— перестановка на множестве , при которой ,
и т. д. Как правило, природа переставляемых элементов не важна, и их считают числами . Перестановок элементов всего .
Перестановки можно перемножать в смысле композиции (как обычные функции), справа налево, при этом снова получается перестановка. Все перестановки на элементах образуют группу . Она называется симметрической группой. Кто знает, почему, пишите в комментариях. И заодно про знакопеременную группу . Автор знает 🙂
Действие перестановки можно наглядно изобразить: отметим вершины и нарисуем стрелку от к , если (в случае рисуем петлю). Получим ориентированный граф, в котором из каждой вершины выходит одно ребро и в каждую вершину входит одно ребро. Этот граф распадается на циклы. Тем самым, перестановка представляется в виде произведения независимых циклов. Неподвижные элементы считаются циклами длины 1 и в записи обычно опускаются. Пример:
Все перестановки делятся на чётные и нечётные. По какому принципу? Есть несколько подходов.
Подход через инверсии. Инверсия в перестановке — это число таких пар , что , но . Чётность перестановки — это чётность числа всех её инверсий. Например, для перестановки
все инверсии суть: , , , , , , . Всего 7 штук, поэтому перестановка (3) нечётная.
Но как с помощью данного определения найти чётность перестановки (1)? Минус этого подхода в том, что в определении перестановки вовсе не предполагается какой-то порядок на множестве, а понятие инверсии основано на порядке.
Отметим, что если фигурки в (1) занумеровать так, как они идут в первой строке, то (1) превратится в (3). Но, что если фигурки занумеровать как-то по другому? Число инверсий может измениться, хотя можно доказать, что их чётность не изменится. Знатоки, конечно, сразу объяснят, почему: при другой нумерации получится сопряжённая перестановка.
Знак перестановки — это число , если перестановка чётная, и число , если она нечётная; обозначения: . Вот главное свойство знака:
При подходе через инверсии оно не очевидно; доказательство требует некоторой возни.
Наконец отметим, что подсчёт инверсий требует время : их наибольшее число равно
и реализуется для перестановки
В то же время любой программист скажет, что определить чётность перестановки легко за линейное время .
Всех этих недостатков лишён подход через транспозиции. Транспозицией называется цикл длины 2 — своего рода простейшая перестановка.
Теорема-определение. Любую перестановку можно представить в виде произведения транспозиций. Чётность их числа в любом представлении одинакова и называется чётностью перестановки.
Всякую перестановку можно представить в виде произведения независимых циклов, а каждый цикл — в виде произведения транспозиций, например, так:
Почему никакую перестановку нельзя одновременно представить в виде произведения чётного и нечётного числа транспозиций? Потому что при умножении перестановки на транспозицию число независимых циклов в её разложении (включая циклы длины 1) меняется на 1. Действительно, если в разложении перестановки элементы и были в одном цикле, то в перестановке этот цикл распадётся на два:
(что верно и при ). А если и были в разных циклах, то эти циклы сольются в один, о чём свидетельствует то же равенство (7), только его надо справа умножить на .
Есть и другое красивое доказательство, использующее многочлен
Надо показать, что он меняет знак при любой транспозиции переменных. Порядок на элементах (переменных) здесь вводится только в доказательстве. (Знатоки, конечно, узнали определитель Вандермонда, но помнят, что обычно определители строятся через перестановки, а не наоборот. Впрочем, можно извратиться. )
Пример. Перестановка (5) есть произведение транспозиций:
Согласно (6) чётность цикла противоположна его длине. Кстати, цикл длины нельзя представить в виде произведения транспозиций. Попробуйте это доказать, модифицировав приведённое выше доказательство. Более общо, перестановку из , которая раскладывается в произведение независимых циклов, можно представить в виде произведения транспозиций и никак не меньше. Это число называется декрементом перестановки. Его преимущество над числом в том, что декремент не зависит от приписывания неподвижных элементов. Так, декремент транспозиции равен 1 при любом .
Итак, вот преимущества подхода через транспозиции.
Грамотное определение, не зависящее от порядка. Например,
Разложение в произведение транспозиций (равно как и разложение на независимые циклы) требует линейное время .
Основное свойство знака (4) очевидно!
P.S. По-видимому, понятие чётности перестановки возникло при решении известной игры «Пятнашки» (почему нельзя переставить 14 и 15 по правилам).
P.P.S. Не говорите «подстановки». Это явно не подходящий в данном контексте термин применяется только в некоторой русскоязычной литературе, причём, в основном, учебной. В англоязычной литературе — только permutations и никаких substitutions. Подстановка (substitution) — это .
Автор: Андрей Канунников, к. ф.-м. н., мехмат МГУ, преподаватель ШАД Хелпер