Как найти подгруппу перестановки - Исправление недочетов и поиск решений вместе с Examum.ru

Consider symmetric group $S_{11}$. I considered the group $H$ generated by permutations
$a=(2,3,4,5,6,7,8,9,10,11,1)$ and $b=(11,10,9,8,7,6,5,4,3,2,1)$. I want to find a group $K$ strictly
larger than $H$ and smaller than $S_{11}$. So I want to get $H subsetneq K subsetneq S_{11}$.
I took some random permutation $c$ and considered the group generated by $(a,b,c)$. But it becomes $S_{11}$. Any idea how to tackle this?

Sorry, probably I am missing. But my Sage code is giving as follows:

n=11
G=SymmetricGroup(n)
a=[2,3,4,5,6,7,8,9,10,11,1]
b=[11,10,9,8,7,6,5,4,3,2,1]

Ha=G.subgroup([a])
print Ha, len(Ha)

Hb=G.subgroup([b])
print Hb, len(Hb)

Hab=G.subgroup([a,b])
print Hab, len(Hab)


Subgroup of (Symmetric group of order 11! as a permutation group) generated by [(1,2,3,4,5,6,7,8,9,10,11)] 11
Subgroup of (Symmetric group of order 11! as a permutation group) generated by [(1,11)(2,10)(3,9)(4,8)(5,7)] 2
Subgroup of (Symmetric group of order 11! as a permutation group) generated by [(1,2,3,4,5,6,7,8,9,10,11), (1,11)(2,10)(3,9)(4,8)(5,7)] 22

Источник

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

Запись
перестановки 
в виде произведения независимых циклов

позволяет легко
найти порядок перестановки

Теорема
2. Порядок
перестановки
(порядок циклической подгруппы)равен
наименьшему
общему кратному (НОК)
длин независимых циклов, входящих в
разложение .

Доказательство. Представим
перестановку
в виде произведения независимых циклов

. (7)

Тогда

Так как
циклы
независимы (они действуют на различных
множествах),
и если q – порядок циклической подгруппы,

то

где
.

Следовательно,
q – общее кратное порядков циклов _k,
которые совпадают с их длинами
.

Если q – наименьшее
положительное число, для которого

,то

. (8)

Основная
теорема арифметики. Каждое
положительное целое число
n не
равное единице может быть записано в
виде произведения простых чисел

.
(9)

Эта запись
единственна с точностью до порядка
следования сомножителей.

Заменив
произведения совпадающих простых чисел
в (9) их степенями, получим

где

Множество простых
чисел

Пример.
Два
любых целых числа m и n можно записать в
виде произведений одних и тех же простых
чисел

тогда

где

Пример. Определить
порядок перестановки
вида

Решение. Представим
перестановку 
в виде произведения независимых циклов,
т.е.

Длины
независимых цикловравны

Следовательно,
порядок рассматриваемой перестановки
равен 28.

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

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

Теорема. Каждая
перестановка
может быть представлена в виде произведения
транспозиции.

Доказательство. Теорема
будет доказана, если мы сможем представить
в виде произведений транспозиций каждый
из циклов _k,
входящих в разложения перестановки:
.

Рассмотрим
произвольный цикл
,
напримери произведем его разложение в произведение
транспозиций.

Алгоритм
разложения цикла
в произведение транспозиций представлен
на рисунке 2.

Цикл
транспозиции

Рис
2.
– Разложение цикла
в произведение транспозиций.

После
завершения всех операций на месте
каждого элемента цикла
оказался следующий за ним элемент, а
первый элемент перешел на последнее
место. Таким образом, циклоказался разложенным в произведение
транспозиций:

Естественно, это
разложение не единственно. Например

Важно
другое – и в первом и во втором его
разложении имеется равное количество
транспозиций – четыре. Если
,
то количество транспозиций равно.
Раскладывая аналогичным образом каждый
циклперестановкив произведение транспозиции, мы получим
разложение всей перестановкив произведение транспозиций.

Замечание. Количество
транспозиций в цикле
может быть и больше четырех! Возьмем
произвольную транспозицию из разложения
этого цикла, например,.
Тогда произведениесовпадает с тождественной перестановкой
и циклможно представить в виде

или

Легко
заметить, что во всех этих случаях число
транспозиций четно и равно 4, 6, 8. Ясно,
что способ, «удлиняющий» разложение,
не изменяет четности исходного разложения.

Теорема. Пусть

– перестановка из
,
а

. (9)

какое-либо
разложение 
в произведении транспозиций.

Тогда число

(10)

называется
четностью (сигнатурой или знаком)
перестановки 
и полностью определяется ,
т.е. не зависит от способа разложения
перестановки 
в произведение транспозиций. Кроме
того, если
,
то

. (11)

Определение. Перестановка
называется четной, если,
и нечетной, если.

Из определения
четности перестановки вытекает, что
все транспозиции – нечетные перестановки.

Действительно,
если
– транспозиция, то,
тогда

Следствие 1. Все
четные перестановки степени n образуют
подгруппу
порядка(она называется знакопеременной группой
степени n).

Следствие 2. Пусть
перестановка
разложена в произведение независимых
циклов

длин

где
,,
…,,
…,– длины независимых циклов.

Тогда

. (12)

Доказательство. Действительно,
по предыдущей теореме имеем

Кроме
того,
поскольку каждыйцикл записывается в виде произведениятранспозиций, то

Соседние файлы в папке ЛЕКЦИИ АиГ

Источник

Вообще говоря, существует несколько подгрупп одного порядка, и они не всегда изоморфны. В $S_4$ есть циклические подгруппы порядка 4 и неизоморфная им клейновская (нормальная).

ага, про клейновскую группу я сам не догадался. Спасибо.

В Вашем случае можно еще пользоваться тем, что порядок элемента подгруппы должен делить порядок подгруппы, и тем, что вместе с каждым элементом в подгруппу входит и порожденная им циклическая группа.

не совсем понимаю, как воспользоваться этим советом. Мне нужно перебрать все 24 элемента группы, и каждый возводить в степень, пока не получится единичная перестановка?

— 19.02.2013, 12:38 —

А сколько всего подгрупп у Вас получилось (считая единичную и саму группу)?

1) 24-го порядка. Одна штука (сама группа)
2) 12-го порядка. Одна штука ( $A_4$ )
3) 8-го порядка. Одна штука (эквивалент многочлену )
4) 6-го порядка. Одна штука (изоморфная $S_6$ , если зафиксировать одно из чисел перестановки)
5) 4-го порядка. Две штуки (циклическая, как вращение куба, и нормальная клейновская)
6) 3-го порядка. Одна штука (циклическая, вращение вокруг оси через диагональ)
7) 2-го порядка. Две штуки (тоже связана с вращениями вокруг осей куба)
1-го порядка. Одна штука (тождественная перестановка)

в итоге получается у меня: 10 штук подгрупп.
Естественно, я считал их по типу подгруппы. Циклических подгрупп 3-го порядка можно выделить четыре штуки (по количеству диагоналей), я считаю их за одну.

Источник

Теорема Кэли позволяет найти для любой конечной группы с определённой бинарной операцией изоморфную ей подгруппу группы всех перестановок.

Теорема Кэли

Теорема (Кэли(Cayley), о вложении любой конечной группы в группу перестановок):

Любая конечная группа порядка изоморфна некоторой подгруппе группы перестановок (подгруппе симметрической группы ).

Доказательство:

(симметрическая группа) — множество перестановок с элементами с операцией .

Пусть — бинарная операция в конечной группе .
Для каждого элемента построим соответствующую перестановку
где .

— перестановка, так как

Для любых таких, что верно, что — инъекция.
Мощность — конечна — биективно, и является перестановкой.

Пусть — композиция двух перестановок.
Если — перестановка, то — обратная перестановка, где — обратный элемент , так как .
Если — нейтральный элемент в группе, то — тождественная перестановка.

Докажем,что множество всех перестановок — подгруппа симметрической группы .

Пусть .Рассмотрим перестановку . Так как — группа, то для любого верно

Так как — группа, то и , откуда . Значит, — подгруппа группы .

Осталось доказать, что и изоморфны. Для этого рассмотрим отображение , которое переводит элемент в элемент , где симметричен элементу в группе .

Заметим, что

Отображение взаимно однозначно.
Для любых верно , то есть отображение сохраняет операцию.

Значит, оно является изоморфизмом групп и .

Примеры

Рассмотрим конечную группу с операцией — сложения по модулю . Найдём подгруппу , изоморфную группе , то есть найдём отображение в .

Пусть

где .

При этом , где — группа всех перестановок с элементами с операцией .

То есть

Тогда находим три перестановки, составляющие группу :

Таким образом, мы нашли подгруппу группы перестановок , изоморфную конечной группе .

См. также

Умножение перестановок, обратная перестановка, группа перестановок
Действие перестановки на набор из элементов, представление в виде циклов
Таблица инверсий
Матричное представление перестановок

Источники информации

Wikipedia — Cayley’s theorem

Источник

Комбинаторика — основные понятия и формулы. Перестановки, размещения, сочетания

Правило умножения
Правило сложения
Размещения и перестановки
Сочетания
Разбиение множества на группы
Задачи контрольных и самостоятельных работ

Основные понятия и формулы

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

Правило умножения (основная формула комбинаторики)

Общее число

способов, которыми можно выбрать по одному
элементу из каждой группы и расставить их в определенном порядке (то есть
получить упорядоченную совокупность

),
равно:

Пример 1

Монету подбросили 3 раза.
Сколько различных результатов бросаний можно ожидать?

Решение

Первая монета имеет

альтернативы – либо орел, либо решка. Для
второй монеты также есть

альтернативы
и т.д., т.е.

Искомое количество
способов:

Правило сложения

Если любые две группы

не имеют общих элементов, то выбор одного
элемента или из

,
или из

,
…или из

можно осуществить

способами.

Пример 2

На полке 30 книг, из них 20 математических, 6 технических и 4
экономических. Сколько существует способов
выбора одной математической или одной экономической книги.

Решение

Математическая книга может быть выбрана

способами, экономическая —

способами.

По правилу суммы существует

способа выбора математической или
экономической книги.

Размещения и перестановки

Размещения – это
упорядоченные совокупности элементов, отличающиеся друг от друга либо составом,
либо порядком элементов.

Размещения без повторений,
когда отобранный элемент перед отбором следующего не возвращается в генеральную
совокупность. Такой выбор называется последовательным выбором без возвращения,
а его результат – размещением без повторений из

элементов по

Число различных способов, которыми можно произвести
последовательный выбор без возвращения

элементов из генеральной совокупности объема

,
равно:

Пример 3

Расписание дня состоит из 5 различных уроков. Определите число
вариантов расписания при выборе из 11 дисциплин.

Решение

Каждый вариант расписания представляет набор 5 дисциплин из 11,
отличающихся от других вариантов как составом, так и порядком следования.
поэтому:

Перестановки – это
упорядоченные совокупности, отличающиеся друг от друга только порядком
элементов. Число всех перестановок множества из

элементов равно

Пример 4

Сколькими способами можно рассадить 4 человек за одним столом?

Решение

Каждый вариант рассадки отличается только порядком участников, то
есть является перестановкой из 4 элементов:

Размещения с повторениями,
когда отобранный элемент перед отбором следующего возвращается в генеральную
совокупность. Такой выбор называется последовательным выбором с возвращением, а
его результат — размещением с
повторениями из

элементов по

Общее число различных способов, которыми можно произвести выбор с
возвращением

элементов из генеральной совокупности объема

,
равно

На сайте можно заказать решение контрольной или самостоятельной работы, домашнего задания, отдельных задач. Для этого вам нужно только связаться со мной:

ВКонтакте
WhatsApp
Telegram

Мгновенная связь в любое время и на любом этапе заказа. Общение без посредников. Удобная и быстрая оплата переводом на карту СберБанка. Опыт работы более 25 лет.

Подробное решение в электронном виде (docx, pdf) получите точно в срок или раньше.

Пример 5

Лифт останавливается на 7
этажах. Сколькими способами могут выйти на этих этажах 6 пассажиров,
находящихся в кабине лифта?

Решение

Каждый из способов
распределения пассажиров по этажам представляет собой комбинацию 6 пассажиров
по 7 этажам, отличающуюся от других комбинаций как составом, так и их порядком.
Так как одном этаже может выйти как
один, так и несколько пассажиров, то одни и те же пассажиры могут
повторяться. Поэтому число таких комбинаций равно числу размещений с
повторениями из 7 элементов по 6:

Сочетания

Сочетаниями

из n элементов по k называются
неупорядоченные совокупности, отличающиеся друг от друга хотя бы одним
элементом.

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

элементов из генеральной совокупности объема

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

элементов по

Число сочетаний из

элементов по

равно:

Пример 6

В ящике 9 яблок. Сколькими
способами можно выбрать 3 яблока из ящика?

Решение

Каждый вариант выбора
состоит из 3 яблок и отличается от других только составом, то есть представляет
собой сочетания без повторений из 9 элементов:

Количество способов,
которыми можно выбрать 3 яблока из 9:

Пусть из генеральной совокупности объема

выбирается

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

элементов по

Число сочетаний с повторениями из

элементов по

ВКонтакте
WhatsApp
Telegram

Подробное решение в электронном виде (docx, pdf) получите точно в срок или раньше.

Пример 7

На почте продают открытки 3 видов. Сколькими способами можно купить
6 открыток?

Решение

Это задача на отыскание числа сочетаний с повторениями из 3 по 6:

Разбиение множества на группы

Пусть множество из

различных элементов разбивается на

групп так, то в первую группу попадают

элементов, во вторую —

элементов, в

-ю
группу —

элементов, причем

.
Такую ситуацию называют разбиением множества на группы.

Число разбиений на

групп, когда в первую попадают

элементов, во вторую —

элементов, в k-ю группу —

элементов, равно:

Пример 8

Группу из 16 человек
требуется разбить на три подгруппы, в первой из которых должно быть 5 человек,
во второй – 7 человек, в третьей – 4 человека. Сколькими способами это можно
сделать?

Решение

Здесь

Число разбиений на 3 подгруппы:

Задачи контрольных и самостоятельных работ

Задача 1

Монету
подбросили 3 раза. Сколько различных результатов бросаний можно ожидать?

Задача 2

Доступ к
файлу открывается, только если введен правильный пароль – определенный
трехзначный номер из нечетных цифр. Какова максимальное число возможных попыток
угадать пароль?

Задача 3

Группу из
10 человек требуется разбить на две непустые подгруппы

. Сколькими способами можно
это сделать?

Задача 4

Два
наборщика должны набрать 16 текстов. Сколькими способами они могут распределить
эту работу между собой.

Задача 5

Шесть
студентов-переводников нужно распределить по трем группам. Сколькими способами
это можно сделать?

ВКонтакте
WhatsApp
Telegram

Подробное решение в электронном виде (docx, pdf) получите точно в срок или раньше.

Задача 6

Лифт
останавливается на 7 этажах. Сколькими способами могут выйти на этих этажах 6
пассажиров, находящихся в кабине лифта?

Задача 7

В ящике 5
красных и 4 зеленых яблока. Сколькими способами можно выбрать 3 яблока из
ящика?

Задача 8

Из ящика,
в котором лежат 10 красных и 5 зеленых яблок, выбирают одно красное и два
зеленых яблока. Сколькими способами можно это сделать.

Задача 9

В группе
из 25 студентов нужно выбрать старосту и 3 членов студенческого комитета.
Сколькими способами можно это сделать.

Задача 10

Акционерное
собрание компании выбирает из 50 человек президента компании, председателя совета
директоров и 10 членов совета директоров. Сколькими способами это можно
сделать?

Задача 11

В
телевизионной студии работают 3 режиссера, 4 звукорежиссера, 5 операторов, 7
корреспондентов и 2 музыкальных редактора. Сколькими способами можно составить съемочную
группу, состоящую из одного режиссера, двух операторов, одного звукорежиссера и
двух корреспондентов.

Задача 12

На группу
из 25 человек выделены 3 пригласительных билета на вечер. Сколькими способами
они могут быть распределены (не более одного билета в руки).

Задача 13

Имеются 7
билетов: 3 в один театр и 4 – в другой. Сколькими способами они могут быть
распределены между студентами группы из 25 человек?

Задача 14

Группу из
16 человек требуется разбить на три подгруппы, в первой из которых должно быть
5 человек, во второй – 7 человек, в третьей – 4 человека. Сколькими способами
это можно сделать?

Правило умножения
Правило сложения
Размещения и перестановки
Сочетания
Разбиение множества на группы
Задачи контрольных и самостоятельных работ

Источник