Задача про группу перестановок

Автор темы Сергей A. 
ОбъявленияПоследний пост
ОбъявлениеИщем преподавателя для углубленного обучения статистическим методам29.05.2020 13:22
ОбъявлениеМатематик-алгоритмист (Vehicle Routing Problem) – удаленная работа03.06.2020 17:58
ОбъявлениеСтуденты и преподаватели мехмата МГУ могут бесплатно получать лицензию на Wolfram Mathematica25.11.2020 00:55
03.01.2004 01:46
Сергей A.
Задача про группу перестановок
Sn - группа перестановок длины n.
An - группа чётных подстановок длины n.
Задача:
а) Найти максимально возможный порядок элемента в этой группе.
б) Найти число различных циклических подгрупп максимального порядка в этой группе.

Задачу решить как для Sn, так и для An.

Народ, помогите, пожалуйста! Наш преподаватель категорически отказывается объяснять, как решается эта задача, а без неё я не смогу получить допуск к зачёту. Если не можете написать решение целиком - хотя бы выскажите идею.

Заранее благодарю, Сергей.
03.01.2004 19:45
По пункту а)
Или я чего-то не понимаю, или это зверская задача.
Если воспользоваться теоремой о разложении перестановки в произведение циклов, то легко видеть, что порядок некоторой перестановки есть наименьшее общее кратное длин циклов, на которые она разлагается.
Т. е. если некоторая перестановка длины n разложена в произведение r циклов длины n_1, n_2, n_3, ... n_r, то порядок этой перестановки есть НОК(n_1, n_2, n_3, ... n_r).
Как максимизировать это число, сходу совершенно не понятно...
Или я что-то прочно забыл?

03.01.2004 21:10
Сергей A.
Всё правильно (+)
Надо найти НАИБОЛЬШЕЕ среди всех наименьших общих кратных длин циклов, на которые разлагается перестановка. Но как это сделать - ума не приложу.

А по пункту "б" - вообще не понятно, как подступиться к этой задаче.
03.01.2004 22:34
Сергей A.
Есть формула (+)
К пункту "б".
У кто-то вывел формулу:
N = k * n! / (f(m)*m), где
n - длина перестановки;
m - максимальный порядок подгруппы;
k - количество различных разложений перестановки длины n на циклы, при которых (при разложениях) НОК максимально.
f(n) - функция Эйлера.

Однако есть две неприятные вещи:
1. Формула работает не всегда.
2. Непонятно, откуда в ней взялась функция Эйлера.

Лично у меня есть следующие соображения.
1. Надо найти разложение: k1+k2+...+ks = n, такое что, НОК(k1, k2, ..., ks) - максимально.
2. Найти, сколькими способами можно заполнить БЕЗ ПОВТОРЕНИЙ s циклов (длины k1, ..., ks соответственно) n натуральными числами - это и будет количеством различных циклических подгрупп максимального порядка.

Поправьте меня, если я не прав.
04.01.2004 01:07
Я сдаюсь
Никаких идей нет :(

Цитата

Сергей A. писал:
Однако есть две неприятные вещи:
1. Формула работает не всегда.
Сергей, но если формула работает не всегда, то это уже не формула :(.
Или у Вас есть надежда ее подправить? Но тогда нужно бы знать, как она получена.

Цитата

Лично у меня есть следующие соображения.
1. Надо найти разложение: k1+k2+...+ks = n, такое что, НОК(k1, k2, ..., ks) - максимально.
2. Найти, сколькими способами можно заполнить БЕЗ ПОВТОРЕНИЙ s циклов (длины k1, ..., ks соответственно) n натуральными числами - это и будет количеством различных циклических подгрупп максимального порядка.

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

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

P.S. Это где ж такой зачет? %(( Это ж ужас! :(

04.01.2004 02:14
Сергей A.
В МГТУ им. Либермана
В МГТУ им. Либермана, тьфу, Баумана на кафедре "Информационная безопасность". :-)

Кстати, отдельное "спасибо" Чашкину А.В. за то, что он очень хорошо нам "объяснил" алгебру, а также за то, что мы очень хорошо "умеем" решать задачи. :-)
04.01.2004 02:28
Сергей A.
P.S.
Разумеется, речь идёт о Чашкине А.В. с кафедры дискретной математики мехмата МГУ. :-)
04.01.2004 04:07
Сергей Михайлов
Иногда верна
Эта формула будет верна тогда и только тогда, когда в любом наборе k_1, ..., k_s, для которого HOK максимален, этот HOK в точности равен произведению k_1*...*k_s. Но для каких n это будет верно, сказать не могу.
04.01.2004 04:18
Сергей Михайлов
Есть ли уверенность в условии?
Может надо не точно вычислить, а оценить?
По-моему, для максимального порядка элемента можно получить оценку e^{n/e}, если я ничего не перепутал в арифметике
04.01.2004 04:24
Сергей A.
Нет, увы, надо вычислить(+)
Нет, увы, надо точно вычислить.
04.01.2004 04:27
Сергей A.
Примечание
Такая задача ставится для небольших n.
n<=20.

В общем случае она явно нерешаемая. :-)
04.01.2004 12:09
Предупреждать надо! :Е
Сергей, для небольших n все подсчитать несложно.
Просто вручную, перебором (нужно только его верно организовать).
Во всяком случае для пункта а). Про б) я еще не успел подумать, но и там, похоже, все не сложно.
P.S. Не надо больше так, хорошо? А то я вчера весь вечер только и думал, как решить Вашу задачку в общем случае...

04.01.2004 13:40
Сергей Михайлов
Ответ для n<=16
Приведена таблица для группы S_n. m - максимальный порядок, f(m) - функция Эйлера. (немного странная запись чисел в таблице вызвана желанием выравнять столбцы)
_n | _m_ |f(m)| соответствующие разбиения n на слагаемые
01 | 001 | 01 | [1]
02 | 002 | 01 | [2]
03 | 003 | 02 | [3]
04 | 004 | 02 | [4]
05 | 006 | 02 | [2, 3]
06 | 006 | 02 | [6], [1, 2, 3]
07 | 012 | 04 | [3, 4]
08 | 015 | 08 | [3, 5]
09 | 020 | 08 | [4, 5]
10 | 030 | 08 | [2, 3, 5]
11 | 030 | 08 | [1, 2, 3, 5], [5, 6]
12 | 060 | 16 | [3, 4, 5]
13 | 060 | 16 | [1, 3, 4, 5]
14 | 084 | 24 | [3, 4, 7]
15 | 105 | 48 | [3, 5, 7]
16 | 140 | 48 | [4, 5, 7]

Для вычисления количества циклических подгрупп максимального порядка при n <=16 можно использовать формулу k*n!/(m * f(m))
Метод разумного перебора, я думаю, позволяет добраться и до 20, но на это мне надо еще где-то час времени, а времени нынче не хватает :) Вот до 16 доходится быстро и легко.

04.01.2004 15:16
Сергей A.
Извините(+)
Извините, забыл.
Но решение задачи в общем случае также представляет интерес. :-)

Кстати, а как быть для An?
04.01.2004 15:30
Сергей Михайлов
рекомендации для A_n
Для начала по пункту а).
Нужно, чтобы элемент максимального порядка оказался четной перестановкой - тогда он лежит в A_n. Здесь можно использовать два правила: 1) при перемножении перестановок их четности складываются; 2) четность цикла длины k равна четности числа (k-1).
С учетом этих правил теперь надо искать таки наборы k_1, ..., k_s, что сумма k_1 + ... + k_s = n, НОК(k_1, ..., k_s) максимально и еще количество четных чисел среди k_1, ..., k_s само четно (это даст четность перестановки, получаемой перемножением циклов с длинами k_1, ..., k_s). Т.е. снова получится перебор, только с большим числом условий.

04.01.2004 16:35
Сергей A.
С методикой вроде разобрался, но (+)
С методикой решения задачи вроде разобрался, но как вы думаете, откуда берётся эта формула? Хотелось бы знать. :-)
04.01.2004 17:11
Сергей Михайлов
как получить формулу
Пусть n - длина перестановки, m - максимальный порядок элемента, и пусть есть k наборов (k_1, ..., k_s) на которых реализуется максимум.
Для определенности рассмотрим одни такой набор. Посмотрим, сколько из него можно организовать элементов максимального порядка. Фактически нам надо расставить произвольно без повторений числа от 1 до n - это n! способов. Вот только мы некоторые элементы получили по несколько раз из-за того, что циклы (234), (342), (423) - это на самом деле один и тот же цикл. Вообще, цикл длины t был посчитан t раз. Таким образом, каждый максимальный элемент мы посчитали k_1*k_2*...*k_s раз (первый цикл можно "представить" k_1 способами, независимо от него второй цикл можно "представить" k_2 способами и т.д.). Таким образом, число элементов максимального порядка будет равно n!/(k_1*...*k_s) - это для одного набора k_1, ..., k_s.
Надо такое проделать для каждого из имеющихся k наборов - так мы посчитаем вообще все элементы максимального порядка в группе S_n - получится сумма по всем максимизирующим наборам k_1, ..., k_s выражения n!/(k_1*...*k_s).
Теперь рассмотрим все циклические группы подгруппы максимального порядка. Каждая такая группа порождена каким-то элементом максимального порядка, причем элементы максимального порядка из разных подгрупп не могут совпадать (иначе совпадали бы сами подгруппы). Но количество порождающих элементов в циклической группе порядка m равно f(m), поскольку если элемент g - порождающий, то элемент g^x будет порождающим если и только если x и m взаимно просты, а количество элементво, взаимно простых с m равно f(m). Итак, если N - число групп, то число элементов максимального проядка равно N*f(m).
Значит, N*f(m) = сумма(n!/(k_1*...*k_s)) по всем максимизирующим (k_1, ..., k_s).
Заметим теперь еще, что если все k_1, ..., k_s - попарно взаимно просты, то m = HOK(k_1, ..., k_s) = k_1*...*k_s. Значит, если в каждом максимизирующем наборе все k_i попарно взаимно просты, то сумма(n!/(k_1*...*k_s)) = k*n!/m, где k - число максимизирующих наборов.
Таким образом, получаем написанную ранее вами формулу
N = k*n!/(m*f(m))
и получаем условия, когда ею можно пользоваться

04.01.2004 18:40
Сергей A.
Сергей, большое вам спасибо! (+)
Без вас я вряд ли догадался бы. :-)
04.01.2004 18:56
Сергей A.
Ещё вопрос (+)
А почему цикл длины m имеет порядок m?
Откуда это следует?
04.01.2004 19:01
Сергей A.
А также не совсем понятно(+)
Почему существует только t одинаковых циклов длины t. Как это доказать?
Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

Кликните здесь, чтобы войти