Главная
В теории групп циклическая перестановка — это перестановка элементов некоторого множества X, которая переставляет элементы некоторого подмножества S множества X циклическим образом, сохраняя на месте остальные элементы X (т.е. отображая их в себя). Например, перестановка {1, 2, 3, 4}, переводящая 1 в 3, 3 в 2, 2 в 4 и 4 в 1 является циклической, в то время как перестановка, переводящая 1 в 3, 3 в 1, 2 в 4 и 4 в 2 циклической не является.
Цикл в перестановке — это подмножество элементов, которые переставляются циклическим образом. Множество S называется орбитой цикла. Каждую перестановку конечного множества элементов можно разложить в объединение циклов с непересекающимися орбитами. В некоторых контекстах циклическая перестановка сама по себе называется циклом.
Определение
Перестановка называется циклической тогда и только тогда, когда она состоит из единственного нетривиального цикла (т.е. цикла длиной больше 1).
Пример:
( 1 2 3 4 5 6 7 8 4 2 7 6 5 8 1 3 ) = ( 1 4 6 8 3 7 2 5 4 6 8 3 7 1 2 5 ) = ( 146837 ) ( 2 ) ( 5 ) {displaystyle {egin{pmatrix}1&2&3&4&5&6&7&84&2&7&6&5&8&1&3end{pmatrix}}={egin{pmatrix}1&4&6&8&3&7&2&54&6&8&3&7&1&2&5end{pmatrix}}=(146837)(2)(5)}Некоторые авторы ограничивают определение только теми перестановками, которые имеют в точности один цикл (то есть, не разрешаются перестановки, имеющие фиксированные точки.
Пример:
( 1 2 3 4 5 6 7 8 4 5 7 6 8 2 1 3 ) = ( 1 4 6 2 5 8 3 7 4 6 2 5 8 3 7 1 ) = ( 14625837 ) {displaystyle {egin{pmatrix}1&2&3&4&5&6&7&84&5&7&6&8&2&1&3end{pmatrix}}={egin{pmatrix}1&4&6&2&5&8&3&74&6&2&5&8&3&7&1end{pmatrix}}=(14625837)}Более формально, перестановка множества X, которая является биективной функцией σ : X → X {displaystyle sigma :X o X} , называется циклической, если действие на X подгруппы с генератором σ {displaystyle sigma } имеет максимум одну орбиту из более чем одного элемента. Это понятие чаще всего используется, когда X является конечным множеством. Тогда, конечно, наибольшая орбита S также конечна. Пусть s 0 {displaystyle s_{0}} — любой элемент S, положим s i = σ i ( s 0 ) {displaystyle s_{i}=sigma ^{i}(s_{0})} для любого i ∈ Z {displaystyle iin mathbf {Z} } . Если множество S конечно, имеется минимальное число k ⩾ 1 {displaystyle kgeqslant 1} , для которого s k = s 0 {displaystyle s_{k}=s_{0}} . Тогда S = { s 0 , s 1 , … , s k − 1 } {displaystyle S={s_{0},s_{1},ldots ,s_{k-1}}} и σ {displaystyle sigma } является перестановкой, определённой формулой
σ ( s i ) = s i + 1 {displaystyle sigma (s_{i})=s_{i+1}quad } для 0 ≤ i < k {displaystyle 0leq i<k}и σ ( x ) = x {displaystyle sigma (x)=x} для любого элемента X ∖ S {displaystyle Xsetminus S} . Элементы, не фиксируемые отображением σ {displaystyle sigma } , можно представить как
s 0 ↦ s 1 ↦ s 2 ↦ ⋯ ↦ s k − 1 ↦ s k = s 0 {displaystyle s_{0}mapsto s_{1}mapsto s_{2}mapsto cdots mapsto s_{k-1}mapsto s_{k}=s_{0}} .Цикл можно записать с использованием компактной циклической записи σ = ( s 0 s 1 … s k − 1 ) {displaystyle sigma =(s_{0}~s_{1}~dots ~s_{k-1})} (запятая между элементами в такой записи не ставится, чтобы избежать путаницы с кортежами). Длина цикла — это число элементов его наибольшей орбиты. В циклической записи циклы длины 1 часто опускаются, если это не вызывает путаницы.
Основные свойства
По одному из основных свойств симметрических групп, любую перестановку можно представить как произведение непересекающихся циклов (более точно — циклов с непересекающимися орбитами). Такие циклы можно переставлять друг с другом, и выражение перестановки единственно с точностью до порядка циклов (заметим, что циклическая запись не единственна — любой k-цикл сам по себе может быть записан k различными способами в зависимости от выбора s 0 {displaystyle s_{0}} в его орбите). Мультимножество длин циклов (цикловый тип) однозначно определяется перестановкой.
Число различных циклов длины k в симметрической группе Sn задаётся для 1 ⩽ k ⩽ n {displaystyle 1leqslant kleqslant n} следующей формулой
( n k ) ( k − 1 ) ! = n ( n − 1 ) ⋯ ( n − k + 1 ) k = n ! ( n − k ) ! k {displaystyle {inom {n}{k}}(k-1)!={frac {n(n-1)cdots (n-k+1)}{k}}={frac {n!}{(n-k)!k}}}Цикл длины k имеет чётность (−1)k − 1.
Транспозиции
Цикл, состоящий из двух элементов, называется транспозицией. Например, перестановка {1, 4, 3, 2}, переводящая 1 в 1, 2 в 4, 3 в 3 и 4 в 2 является транспозицией (а именно, транспозицией, переставляющей 2 и 4).
Любую перестановку можно представить как композицию (произведение) транспозиций — формально, они являются генераторами группы. Более того, любую перестановку упорядоченного множества X = {1, 2, …, n} можно выразить как произведение смежных транспозиций, то есть транспозиций вида ( k k + 1 ) . {displaystyle (k~~k+1).} Действительно, любую транспозицию можно представить в виде произведения смежных транспозиций.
Разложение перестановки в произведение транспозиций можно получить, например, путём выписывания перестановки как произведения различных циклов, а затем итеративного разложения циклов длины 3 и более в произведение транспозиции и цикла на единицу короче:
( a b c d … y z ) = ( a b ) ⋅ ( b c d … y z ) {displaystyle (a~b~c~d~ldots ~y~z)=(a~b)cdot (b~c~d~ldots ~y~z)}Симметрическая группа является группой Коксетера, в том смысле, что она порождается элементами порядка 2 (смежными транспозициями) и все соотношения имеют определённый вид.
Один из главных результатов элементарной теории симметрических групп утверждает, что либо все разложения данной перестановки на транспозиции имеют чётное число транспозиций, либо все разложения имеют нечётное число транспозиций. Это позволяет чётности перестановки быть хорошо определённой функцией.