Циклічна перестановка

Перестановка 8-ми елементів одним циклом.

В математиці, і зокрема в теорії груп, цикл — перестановка елементів деякої множини X, яка відображає елементи деякої підмножини S в X один в інший циклічним чином, тоді як інші елементи X залишаються фіксованими. Наприклад, перестановка {1, 2, 3, 4}, що переставляє 1 в 3, 2 в 4, 3 в 2 і 4 в 1 є циклом, тоді як перестановка 1 в 3, 2 в 4, 3 в 1 і 4 в 2 ні (це окремі пари {1, 3} і {2, 4}). Множина S називається орбітою циклу.

Визначення

Перестановка 8-ми елементів з двома фіксованими елементами та одним циклом на 6 елементів

.

Перестановка множини X, яка бієктивною функцією $\sigma :X\to X$, називається циклом, якщо дія на X підгрупи утвореної $\sigma$ має саме одну орбіту з більш як одним елементом. Це поняття найчастіше вживають коли X скінченна множина; тоді й орбіта S скінченна. Нехай $s_{0}$ довільний елемент з S, і покладемо $s_{i}=\sigma ^{i}(s)\,$ для будь-якого $i\in \mathbf {Z}$. З того, що по припущенню S містить більше ніж один елемент, $s_{1}\neq s_{0}$; якщо S скінченна, існує мінімальне число $k>1$ для якого $s_{k}=s_{0}$. Тоді $S=\{s_{0},s_{1},\ldots ,s_{k-1}\}$, і $\sigma$ є переставка визначена

$\sigma (s_{i})=s_{i+1}\quad {\mbox{for }}0\leq i<k$

і $\sigma (x)=x$ для будь-якого елементу з $X\setminus S$. Елементи не зафіксовані $\sigma$ можна зобразити як

$s_{0}\mapsto s_{1}\mapsto s_{2}\mapsto \cdots \mapsto s_{k-1}\mapsto s_{k}=s_{0}$.

Цикл можна записати за допомогою циклічного запису $\sigma =(s_{0}~s_{1}~\dots ~s_{k-1})$ (коми тут не вживаються з метою уникнення плутанини з k-кортежем). Довжина циклу — це кількість елементів його орбіти. Цикл довжини k також звуть k-цикл.

Основні властивості

Перестановка 8-ми елементів з двома фіксованими елементами та двома циклами

.

Один з головних вислідів у симетричних групах стверджує, що будь-яку перестановку можна виразити як добуток неперетинних циклів (точніше: циклів з неперетинними орбітами); такі цикли комутують між собою, і вираз перестановки унікальний з точністю до порядку циклів (але зверніть увагу, що циклічний запис не унікальний: кожен k-цикл сам по собі може бути представлений k різними способами, в залежності від вибору $s_{0}$ в його орбіті). Отже мультимножина довжин циклів в цьому виразі унікально визначає перестановку, парність і клас спряженості перестановки в симетричній групі також визначаються цим.

Кількість k-циклів у симетричній групі S_n для $2\leq k\leq n$ дається такими тотожними формулами

${\binom {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).

Джерела

• В.А. Вишенський, М.О. Перестюк. Комбінаторика: перші кроки. — Кам'янець-Подільський : Аксіома, 2010. — 324 с. — ISBN 978-966-496-136-0.(укр.)