Подстановки, перестановки

Определение 6. Пусть — разложение подстановки в произведение транспозиций. Предложение 2. Каждая подстановка может быть представлена в виде произведения транспозиций. Предложение 1. Любая подстановка из может быть разлжена в произведение попарно независимых циклов.

Определение 4. Циклы называются независимыми5), если они не имеют общих действительно перемещаемых символов. Такое представление определено однозначно с точностью до порядка перемножения циклов. Тогда число называется знаком7)(четностью) подстановки . Подстановка называется четной8), если и нечетной9) в противном случае. Заметим еще, что запись цикла в виде неоднозначна.

Количество чисел, действительно перемещаемых циклом а, называется его длиной. Из сказанного выше ясно, что длина цикла равна его порядку. Задача. Доказать, что подстановка, действительно перемещающая только два числа, является транспозицией.

Действительно, если, например, то, применяя к этому равенству подстановку мы получим что в силу минимальности числа q невозможно. Так как каждый цикл разлагается на транспозиции, то из доказанной теоремы следует, что любая подстановка разлагается в произведение транспозиций (уже, вообще говоря, не независимых). Числа, входящие в независимые циклы, на которые разложена некоторая подстановка, суть числа, действительно перемещаемые этой подстановкой.

Таким образом, количество и строение независимых циклов, на которые разлагается подстановка, однозначно определяются этой подстановкой. Перед тем, как приступить к рассказу о подстановках в системе GAP, приведем необходимые теоретические сведения. Взаимно однозначное отображение множества M первых n натуральных чисел на себя называется подстановкой n-й степени. Далее, подстановка s называется циклом длины k, если s(a1)=a2, s(a2)=a3, … s(ai)=ai+1 и s(ak)=a1 (разумеется, все элементы, входящие в один цикл, должны быть попарно различны).

Каждая подстановка разлагается в произведение конечного числа транспозиций, количество которых определяет четность подстановки. Подстановки являются стандартными объектами в системе GAP. При этом ввод и вывод подстановок производится в виде произведения независимых циклов. Подстановки в GAP не принадлежат к какой-либо специфической группе подстановок. Это означает, что Вы можете работать с ними, не определяя группу подстановок, которой они принадлежат.

Подстановки, перестановки

Аргументом этих функций может быть одна подстановка, список подстановок, или, например, группа подстановок или ее класс сопряженных элементов. Действие этих функций описывается в следующей таблице. Возвращает множество положительных чисел, которые перемещаются данной подстановкой. Знак подстановки является гомоморфизмом из симметрической группы подстановой в мультипликативную группу { +1, -1 }, ядром которого является знакопеременная группа.

Ее результатом является список, i-й элемент которого содержит количество циклов длины i+1. Если подстановка не содержит циклов длины i+1, то i-й элемент списка не определен. Циклы длины 1 игнорируются. Функция ListPerm(perm) возвращает список, который содержит образы положительных чисел под действием подстановки perm, т.е. list = i^perm, где i изменяется от 1 до LargestMovedPoint(perm).

Разложение подстановок на циклы.

Как известно, это — симметрическая группа подстановок 8-й степени. Подстановки удобно записывать в циклической форме. При такой записи индексы, остающиеся на месте, обычно не пишутся. Элементарная циклическая подстановка, переставляющая два любых индекса i и j, называется транспозицией. Транспозиции, фигурирующие в формулах (2.25) и (2.26), связанные, так как имеют какой-либо общий индекс.

Четность произведения подстановок

Используя указанные свойства подстановок, записанных в циклическом виде, можно составить несколько полезных правил, которые сделают процедуру их перемножения почти механической. Если декремент и число инверсий являются нечетными, то и число транспозиций также будет нечетным. К сказанному добавим: тождественная подстановка e четна, любая транспозиция — нечетна.

С подстановками можно встретиться и при решении задач прикладной математики, в частности, при вычислении определителей. Погодите, но ведь цикл может быть одноэлементным.

В любой нетривиальной перестановке несколько (возможно, ноль) начальных элементов отображаются каждый в себя, а следующий за ними — уже во что-то другое. Комбинаторика – раздел математики, посвященный решению задач выбора и расположения элементов некоторого, обычно конечного, множества в соответствии с заданными правилами.

Правило суммы. Если объект А может быть выбран m способами, а объект В другими n способами, то выбор “либо А, либо В” может быть осуществлен m+n способами. Следует заметить, что в первом правиле выборы А и В являются взаимно исключающими, т.е. нет возможности выбрать оба объекта одновременно (одним и тем же путем).

Перестановками из n элементов называются соединения, каждое из которых содержит n элементов и которые отличаются между собой лишь порядком расположения элементов. В первой перестановке все числа идут в натуральном порядке, а в остальных перестановках этот порядок нарушен.

Любой цикл длины является произведением транспозиций

Пример:Подсчитать число инверсий в перестановке 531642. Операция перемещения двух элементов в данной перестановке называется транспозицией. Перестановку называют четной (или четного класса), если число ее инверсий четное, и нечетной (нечетного класса) в противном случае. Но если применить к ней транспозицию (2, 3), то получим перестановку 321 с тремя инверсиями, т.е. нечетную перестановку. 1. Чтобы перейти от одной перестановки к другой того же класса, надо выполнить четное число транспозиций.

Очевидно, что различные подстановки из n чисел должны иметь в нижней строке запись ( 3 ) различные перестановки. Подстановку n – й степени называют четной, если нижняя строка ее записи ( 3 ) образует четную перестановку, и нечетной, если эта строчка образует нечетную перестановку.

Таким образом, знак подстановки равен 1, если она четная, и -1, если она нечетная. Другими словами, разложение подстановки в произведение независимых циклов однозначно (с точностью до порядка множителей). Оказывается, что любая не тождественная подстановка является произведением независимых циклов. Для обозначения цикла используют запись , где — число действительно перемещаемых символов подстановки, которое называется длиной цикла4).

Не проходите мимо: