Транспозиции, разложение в циклы, перестановки

[dmitryf]

Привет!

Помогите разобраться с перестановками, транспозициями, циклами.

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

Определение. Цикл длины 2 называется транспозицией. Ок.

Следствие. Каждая перестановка является произведением транспозиций. Тут начинаются противоречия. И я не совсем понимаю алгоритм разложения перестановки на произведения транспозиций ( с циклами все ясно).

Например,

Перестановка (она же цикл) (1 2 3) = (1 3)(1 2), здесь в двух транспозициях учавствует еденица, но ведь циклы должны быть независимы? Или транспозиция все-таки не просто цикл.

Дальше разложений может быть несколько:
(1 2 3) = (1 3)(1 2) = (2 3)(1 3) = (1 3)(2 4)(1 2)(1 4)

А как же тогда однозначное разложение.

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

Спасибо.

[gris]

А с чего Вы взяли, что подстановка разлагается в произведение транспозиций однозначно? Эти маленькие циклы уже не будут независимы. И число множителей в разложениях может отличаться, правда чётность числа сомножителей будет постоянной, что видно на Вашем примере.
Насчёт главного вопроса. Посмотрите понятие "декремент подстановки".

Алгоритм разложения на циклы вроде бы очевиден. Берём первый элемент, определяем цикл, который им образуется, потом берём очередной элемент, не вошедший в первый цикл, и строим цикл для него. Так, пока не исчерпаются все элементы.