Число 252 представили в виде произведения

Транспозиции Эти понятия играют важную роль в комбинаторике и мы напомним. Подстановкой называется биекция конечного множества на себя рис. Подстановку часто изображают в виде соответствия между двумя строками: первую строку называют «операндом», вторую — «результатом». Порядок, в котором записывается операнд, вообще говоря, несуществен: Подстановку можно представить, выписывая в строку элементов и подписывая под каждым из них его образ при биекции. Перестановкой множества называется вполне упорядоченное множество, состоящее из всех элементов Если состоит из элементов, то имеется таких множеств. Таким образом, подстановку можно охарактеризовать перестановкой, задаваемой нижней строкой. Пусть — образ элемента при подстановке образ элемента у при подстановке Определим подстановку Например, если то На рис. За единичную подстановку примем Для каждой подстановки существуют симметричная ей слева и симметричная ей справа, совпадающие между собой как на рис. Легко проверить свойство ассоциативности: Таким образом, выполняются все групповые аксиомы. Множество подстановок элементов образует группу, называемую симметрической группой Группа не коммутативна, так как для некоторых элементов Прежде чем ввести понятие цикла, укажем еще одно изображение подстановки, пример которого приведен на рис. С другой стороны, подстановку можно записать с помощью перестановки, если первые строки всех подстановок взять одинаковыми. Пусть задана биекция подмножества а на. Если мы проходим, следуя ей, все элементы начиная с некоторого и возвращаясь в него, то получаемую подстановку назовем циклом. Запишем эти подстановки с помощью циклов: Обычно цикл записывают, начиная с наименьшего элемента или с элемента с наименьшим индексов. Например, Часто удобно заменить символы в подстановке на целые числа или на элементы с целочисленными индексами Цикл, состоящий из элементов, называют -циклом. Например, 1652734 на рис. Пусть множество всех подстановок элементов. Разобьем это множество на классы эквивалентности согласно цикловой структуре. Подмножество из образует класс если для каждой подстановки из этого подмножества число -циклов равно число -циклов равно число -циклов равно Пример. Будем иногда писать 0, 0, 1, 1 вместо 0, 0, 1, 1, 0, 0, 0если это не приводит к недоразумению. Теорема Для любого класса подстановок элементов Это очевидно, ибо -цикл содержит элементов, а всего элементов в подстановке Теорема II. Обозначим через число подстановок класса Тогда где Рассмотрим -циклов в подстановке из заданного класса. Так как безразлично, какой элемент брать в качестве начального в каждом из этих циклов, то эту подстановку можно записать различными способами. Учитывая, что циклы можно переставлять между собой, получаем различных способов записи. Следовательно, любую подстановку из класса можно записать способами. Так как всего имеется возможных записей подстановок из этого класса, то получаем 16. Рассмотрим класс 1,0, 1,0 при Тогда Эти подстановки представлены на рис. Определим последовательно Очевидно, что все эти подстановки коммутативны: Например, если то Все степени некоторой подстановки можно изобразить в виде схемы, как это показано на рис. Однако если подстановка обладает несколькими циклами, такая схема громоздка. Аналогично вводятся отрицательные степени: Порядок подстановки. Порядок подстановки есть наименьшее целое положительное число такое, что Например, как это видно из рис. Например, -цикл имеет порядок Теорема III. Порядок подстановки равен наименьшему общему кратному порядков циклов, определяющих класс эквивалентности, которому она принадлежит. Пусть подстановка принадлежит классу Ее всегда можно представить в виде произведения подстановок перестановочных между собойпервая из которых содержит -циклов, вторая содержит -циклов и -циклов, содержит 1-циклов и -циклов. На рис, 22 дан пример такого разложения. Таким образом, В силу коммутативности Для того чтобы была единичной подстановкой, необходимо и достаточно, чтобы Рис. Но наименьшее целое число для которого это свойство выполняется, есть наименьшее общее кратное тех чисел для которых Рис. Транспозиция есть подстановка из класса Она переставляет между собой два элемента, не меняя расположения остальных. Всякая подстановка разлагается в произведение транспозиций. Способ доказательства теоремы проиллюстрируем на примере. Пусть и заданы транспозиции Тогда как видно из рис. Произведение различных транспозиций не коммутативно. Например, но Четность перестановки. Рассмотрим перестановку на множестве из элементов. С этим множеством свяжем неупорядоченное множество образованное парами различных элементов причем элементы в каждой паре записываются в том же порядке, что и. Например, с перестановкой получающейся из подстановки на рис. С другой перестановкой получающейся из подстановки на рис. Часть пар в совпадают, а другие отличаются порядком их элементов. Пусть число таких инверсий. Если четно, то скажем, что имеет ту же четность, что. Отношение имеют одинаковую четность» есть отношение эквивалентности рефлексивность, симметричность и транзитивность очевидны. Так как всего имеется перестановок и каждый класс содержит одно и то же число элементов, то это число равно Исходная перестановка рассматривается как четная. Подстановка сопоставляет любой перестановке перестановку. Например, если то или символически По последовательности перестановок и подстановке можно выписать последовательность образов Четности и либо все одинаковы, либо все противоположны Действительно, определим подстановку Рассматривая как нижние строки соответствующих подстановок, имеем Отсюда следует, что число инверсий при переходе от совпадает с числом инверсий при переходе от Таким образом, подстановки также распадаются на два класса подстановка принадлежит четному классу. Имеется четных подстановок и столько же нечетных. Группы и подгруппы подстановок. Рассмотрим все подстановки множества из элементов. Как было показано, они образуют группу, элементы которой можно разбить на два класса: четных и нечетных подстановок. Четные подстановки образуют подгруппу: 1 единичная подстановка четна по определению; 2 обратная к четной подстановке также четная; 3 произведение четных подстановок четно. Сформулируем еще несколько теорем. Теорема Всякая транспозиция есть нечетная подстановка. Теорема очевидна в силу определения транспозиции. Так как произведение транспозиций дает четную подстановку, а произведение транспозиций — нечетную, то справедливо следующее утверждение: Теорема VI. Если подстановка разложена в произведению транспозиций, то число их четно или нечетно в зависимости от того, четна или нечетна Верно и обратное утверждение. Если число четных циклов четно, то подстановка четна, если это число нечетно, то подстановка нечетна. Подстановки класса 1, 2, 0, 1, 0, 0, 0, 0, 0 нечетны, так как содержат четных циклов Подстановки класса 0, 1, 1, 1, 0, 0, 0, 0, 0 четны, так как содержат четных циклов. Подстановки класса 3,0, 1,0, 0,0 четны, так как не содержат четных циклов. Теорема VIII теорема Кэли. Всякая конечная группа изоморфна некоторой группе подстановок ее элементов. Доказательство предоставим читателю в виде упражнения. © Научная библиотека Копирование информации со страницы разрешается только с указанием ссылки на данный сайт.