Как найти произведение перестановок

Перестановка порядка n это биективное отображение конечного множества из n элементов  в себя.

Таблица вида  

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

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

Пример вычисления произведения перестановок: если

При помощи обычного определения удобно вычислять произведение так: в перестановке σ переставляем столбцы так, что первая строчка в σ совпадает с последней строчкой в τ . Тогда произведением будет перестановка, у которой первая строчка — стандартная, а вторая строчка — это вторая строчка из σ.

Пример 1:

Пример 2. Найти произведение перестановок можно и так

Первая перестановка переводит один в два, а вторая два в семь, значит произведение переводит один в семь и т.д.

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

Например: στ= (1,2,4,3) · (1,3) = (2,4,3)

При этом произведение получается так: для каждого элемента от 1 до 4 надо пройти по циклам в левой части и проследить куда он переходит.

В частности, 3 сначала переходит в 1 (цикл (1 , 3)),

а затем 1 в 2 (цикл(1 , 2 , 4 , 3)).
Значит в произведении 3 будет переходить в 2.

Умножение перестановок некоммутативно:  τσ ≠ στ.

Следовательно решение уравнений вида:  τx = σ,  xτ = σ

x = τ^-1σ,   x = στ^-1