Транспозиция и перестановки

Тождественное отображение Xn в себя называют единичной перестановкой и часто обозначают через e:

Транспозицией элементов i и j, где i, j ∈ Xn и i ≠ j, называют перестановку τ_i,j , которая меняет местами i и j, а остальные элементы оставляет на месте.

Пример 1, при n = 7

Транспозицию τ_i,j называют простой (или смежной), если j = i + 1.

Например,τ_1,2  и τ_4,5 — простые транспозиции.

Пример 2. (1 2 5 4 3) = (3 5)

Любая перестановка разлагается в произведение транспозиций (разложение неоднозначно!):

Для получения этого разложения используется формула:

представляющая разложение цикла в произведение транспозиций.