Коммутирующие подстановки

[elfirina]

ET в сообщении #1117824 писал(а):

elfirina в сообщении #1117799 писал(а):

Ребят, ну подскажите кто-нибудь: это верно или нет?

Нет

Что ж, я полагаю, что ошибка у меня та же, о которой и говорила мне provincialka, а именно, в представлении цикла. Можете мне подсказать, можно ли решить эту задачу, не используя понятия централизатор, как предложил lek? И, если можно, то как?

[ET]

Ошбка у вас в том, что вы совсем непонятно что делаете, никак не относящееся к делу. Ну, хорошо, получили вы эти свои 25. Ну прсто подумайте: у вас группа $S_{15}$ А если бы было $S_{20}$ и та же подстановка? По-вашему число коммутирующих элементов не изменилось бы? А ничего, что тогда к ним добавились бы всякие (19,20)?
Я, честно говоря очень давно все это проходил, но сразу увидел, что число коммутирующих с вашей подстановкой не меньше чем $5\cdot5!$ , а потом, после коммента в этой теме увидел и $5\cdot5\cdot5!$ Правда, чтобы доказать, что других нет надо уже многое вспоминать, а времени нет
А чем вас так не устраивает понятие централизатор? Ведь по сути вы в этой теме спросили про централизатор конкретного элемента в $S_{15}$

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

[andyzt]

Вы тоже поступаете в Школу анализа данных Яндекса? :) Правильный ответ к этой задаче - 6000. Подсчет состоит из 3-х частей:
1) элементы 2,6,8,12,13 - они не перемещаются. Поэтому с ними коммутирует любая подстановка на этих 5 элементах. Таких $5! = 120$
2) Подстановки, которые оставляют элементы внутри циклов по 5 элементов. Таких 5 для первого цикла и 5 для второго, итого 25 шт
3) Подстановки, которые переводят элемент первого цикла в элемент второго. Коммутируют только те из них, которые чередуют элементы циклов, т. е. например (1, 4, 3, 7, 14, 15, 10, 9, 11, 5). При чем первый переход может быть выбран 5 способами (1 - (элемент 2-го цикла)). Обратный переход (4 - 3) так же может быть выбран 5 способами (включая перестановку 4 -1). Все остальные элементы однозначно определяются из этих двух. Итого 25 вариантов

Используя утверждение, что перестановки на независимых элементах всегда коммутативны, перемножаем $(25+25)$\cdot$120 = 6000 $

[bsl]

Цитата:

Вы тоже поступаете в Школу анализа данных Яндекса? :) Правильный ответ к этой задаче - 6000. Подсчет состоит из 3-х частей:
1) элементы 2,6,8,12,13 - они не перемещаются. Поэтому с ними коммутирует любая подстановка на этих 5 элементах. Таких $5! = 120$
2) Подстановки, которые оставляют элементы внутри циклов по 5 элементов. Таких 5 для первого цикла и 5 для второго, итого 25 шт
3) Подстановки, которые переводят элемент первого цикла в элемент второго. Коммутируют только те из них, которые чередуют элементы циклов, т. е. например (1, 4, 3, 7, 14, 15, 10, 9, 11, 5). При чем первый переход может быть выбран 5 способами (1 - (элемент 2-го цикла)). Обратный переход (4 - 3) так же может быть выбран 5 способами (включая перестановку 4 -1). Все остальные элементы однозначно определяются из этих двух. Итого 25 вариантов

Используя утверждение, что перестановки на независимых элементах всегда коммутативны, перемножаем $(25+25)$\cdot$120 = 6000 $

Тоже ищу решение этой задачи. Наткнулся на ваше. Пока пытаюсь переварить второй пункт :) Подскажите, как сделан вывод, что коммутирующих подстановок в каждом цикле из 5 элементов по 5 штук? Программно проверил - действительно по 5. А как это на глаз оценить? Может быть, ответ очевидный, но я прям задумался.

[andyzt]

На глаз оценить не получится, но это довольно известный факт.
1-я часть простая: найти, что найдется 5 подстановок, которые коммутируют. Это будут подстановки, полученные из исходного цикла, умноженного на себя n раз (n от 1 до 5, 5 даст тождественную подстановку). Понятно, что они коммутируют, т.к. в результате получается подстановка из цикла умноженного n+1 раз на себя.
2-я часть - доказать что другие подстановки не коммутируют. Для этого введем понятие сдвига (это моя идея, наверняка можно проще). Пусть есть исходный цикл длины 5 из элементов (12345). У него сдвиг каждого элемента равен 1 (т.е 1 -2, 2 - 3 и т.п.). Теперь любая подстановка на этих 5 элементах, которая не является произведением этого цикла будет иметь разные сдвиги хотя бы для 2-х соседних элементов (например у цикла (14325) сдвиги будут равны (33-1-11). Тогда 1-й элемент из пары с неравными сдвигами коммутировать не будет. В данном случае берем сдвиг 3 и -1, первый элемент это 2. В одном случае 2 сдвигается на 1, потом на -1, в другом на 3 затем на 1. Таким образом в любой подстановке с разными сдвигами найдется элемент, который не коммутирует. Цикл 12345 получается из нашего цикла сменой нумерации элементов, поэтому это верно для любого цикла.

[provincialka]

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

Рассмотрим какой-нибудь цикл $(1,2,3)$, входящий в перестановку $f$. Опишем коммутирующее с ним преобразование $g$. Если $g(1)=x$, то $f(x)=f(g(1))=g(f(1))=g(2)$. Таким образом, значения $g(2), g(3)$ определяются однозначно и составляют также цикл, входящий в $f$.

В нашем примере есть два цикла длиной $5$. Каждый из них можно отобразить либо в себя, либо во второй цикл той же длины. Причем для каждого цикла есть $5$ таких отображений. Всего получаем $2!\cdot 5^2=50$ возможностей. Аналогично циклы длиной $1$ переходят друг в друга, всего таких перестановок $5!\cdot 1^5=120$. Перемножая два числа и получим ответ.

[myltykritik]

Здравствуйте!

Вот тут в пункте 3 говорится, что

Цитата:

Обратный переход (4 - 3) так же может быть выбран 5 способами (включая перестановку 4 -1).

Не понимаю, почему включая перестановку (4 - 1).
Мы же на первом шаге уже выбрали один элемент, почему можем его выбрать и на обратном шаге?

andyzt в сообщении #1118355 писал(а):

Вы тоже поступаете в Школу анализа данных Яндекса? :) Правильный ответ к этой задаче - 6000. Подсчет состоит из 3-х частей:
1) элементы 2,6,8,12,13 - они не перемещаются. Поэтому с ними коммутирует любая подстановка на этих 5 элементах. Таких $5! = 120$
2) Подстановки, которые оставляют элементы внутри циклов по 5 элементов. Таких 5 для первого цикла и 5 для второго, итого 25 шт
3) Подстановки, которые переводят элемент первого цикла в элемент второго. Коммутируют только те из них, которые чередуют элементы циклов, т. е. например (1, 4, 3, 7, 14, 15, 10, 9, 11, 5). При чем первый переход может быть выбран 5 способами (1 - (элемент 2-го цикла)). Обратный переход (4 - 3) так же может быть выбран 5 способами (включая перестановку 4 -1). Все остальные элементы однозначно определяются из этих двух. Итого 25 вариантов

Используя утверждение, что перестановки на независимых элементах всегда коммутативны, перемножаем $(25+25)$\cdot$120 = 6000 $