Задача на перестановки.

[timas-cs]

Правильно ли я сделал задачу на перестановки?
На множестве ${1,2,3,4,5,6}$ заданы перестановки $\pi=\begin{pmatrix} 1 2 3 4 5 6 \\ 3 4 2 5 6 1 \end{pmatrix}$ и $\tau = (136)(245)$. Найти $({\pi \circ \tau })^{-25}$.
Я представил $\tau$ как $\begin{pmatrix} 1 2 3 4 5 6 \\ 2 3 4 6 1 5 \end{pmatrix}$ потом ${\pi \circ \tau }$ и получил $\begin{pmatrix} 1 2 3 4 5 6 \\ 4 6 3 1 5 2 \end{pmatrix}$, а это тоже самое, что и $(1)(2)(3)(4)(5)(6)$. То есть $({\pi \circ \tau })^{-25}=(1)(2)(3)(4)(5)(6)$.

[Metford]

timas-cs в сообщении #1207927 писал(а):

а это тоже самое, что и $(1)(2)(3)(4)(5)(6)$

А это так?

[timas-cs]

Metford, если я правильно разобрался-$(14)(26)(3)(5)$, и в степени $-25$ тоже самое.

-- 09.04.2017, 19:32 --

Metford Правильно?

[iifat]

Вам бы переписать всё с самого начала. $\tau$ у вас в первом сообщении какое-то странное, и разложение произведения на циклы в стартовом тоже очень странное. В третьем, может, и правильное, но $\tau$-то это не отменяет!

[timas-cs]

iifat
Хорошо. Итак $\tau=(136)(245)=\begin{pmatrix} 1 2 3 4 5 6 \\ 3 4 6 5 2 1 \end{pmatrix}$, тогда произведение будет таким $\begin{pmatrix} 1 2 3 4 5 6 \\ 6 5 4 2 1 3 \end{pmatrix}$, а после возведения в степень получится $ \begin{pmatrix} 1 2 3 4 5 6 \\ 5 4 6 3 2 1 \end{pmatrix}=(152436)$

[crazy_taxi_driver]

Да, и произведение, и ответ - верные.
Ой, нет, извините, неверные.

Действуем на 1: $\tau$: 1->3 $\pi$: 3->2, соответственно $\pi \circ \tau$: 1->2. Вы вычислили произведение $\tau \circ \pi$, и правильно возвели его в -25 степень.

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

gap> tau:=(1,3,6)(2,4,5);
(1,3,6)(2,4,5)
gap> pi:=(1,3,2,4,5,6);
(1,3,2,4,5,6)
gap> pi*tau;
(1,6,3,4,2,5)
gap> (pi*tau)^(-25);
(1,5,2,4,3,6)
gap> tau^-1*pi^-1;
(1,5,2,4,3,6)

[VAL]

timas-cs,
Вы зачем-то переводите перестановку $\tau$ из цикловой записи в двухстрочную.
ГОРАЗДО удобнее поступать ровно наоборот - переводить $\pi$ из двухстрочной записи в цикловую.
В таком виде легко возвести подстановку в любую степень в уме, за доли секунды.

[iifat]

VAL в сообщении #1208207 писал(а):

В таком виде легко возвести подстановку в любую степень в уме, за доли секунды

Ну, легко — это если разложить на непересекающиеся циклы. Алгоритм умножения двух перестановок, записанных в виде непересекающихся циклов, у Кнута читал, но проделать в уме за секунды — как-то, по мне, затруднительно.

[VAL]

iifat в сообщении #1208241 писал(а):

Алгоритм умножения двух перестановок, записанных в виде непересекающихся циклов, у Кнута читал, но проделать в уме за секунды — как-то, по мне, затруднительно.

На 6-элементном множестве? Затруднительно?!
Кроме того, в уме я предлагал возводить в степень результат перемножения. А перемножить можно и на бумажке. Но, все равно, за несколько секунд.

[timas-cs]

VAL Согласен.

Ошибка найдена и исправлена. Неправильно посчитал произведение. Перепутал порядак тау-пи и пи-тау.

[Munin]

Как умножать две перестановки в виде циклов.

Начинаете с первого цикла первой перестановки. Пишете эту цифру: $(k.$ Потом смотрите, куда она перейдёт
1) по своему циклу в $\sigma_1(k)$;
2) из её образа по циклу второй перестановки в $\sigma_2(\sigma_1(k)).$
Пишете после $(k$ этот второй образ. Потом берёте его, ищете в первой перестановке (в любом цикле), и повторяете шаги (1, 2). И так, пока не вернётесь к $k$ - тогда ваш цикл закончен.

Параллельно вычёркиваете, например, в первой перестановке все цифры, которые вы смотрели шагом (1). Начинаете следующий цикл с какой-нибудь невычеркнутой цифры. И так, пока не вычеркнете все (или подчёркиваете, как вам больше нравится).

Процедура обобщается на $n$ множителей.

[arseniiv]

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

[Munin]

А, полезное замечание.