Циклічний запис (комбінаторика)

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

.

Циклічний запис (Шаблон:Lang-en) — це угода щодо запису переставки у вигляді циклів, що в ній є. Також називають коловий запис (Шаблон:Lang-en), а переставку — колова (циклічна) переставка (Шаблон:Lang-en).

Визначення

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

.

Для скінченної множини $S$ з різними елементами

$a_1,\dots ,a_k,k\ge 2$

Вираз $(a_1\dots a_k)$ позначає σ чиїми діями є

$a_1\mapsto a_2\mapsto a_3\mapsto \dots \mapsto a_k\mapsto a_1.$

Для кожного індексу i,

$\sigma (a_i)=a_{i+1},$

де $a_{k+1}$ означає $a_1$.

Існує $k$ різних виразів для того самого циклу; всі наступні представляють один цикл:

$(a_1{a}_2{a}_3\dots a_k)=(a_2{a}_3\dots a_k{a}_1)=\cdots =(a_k{a}_1{a}_2\dots a_{k-1}).$

1-елементний цикл на кшталт (3) — це тотожна переставка. Тотожну переставку також можна записати як порожній цикл, "()".

Приклад

Приведення переставки із двострокового запису у циклічний запис:

$\sigma =\left(\begin{array}{cccccc}1& 2& 3& 4& 5& 6\\ 3& 5& 6& 4& 2& 1\end{array}\right)=\left(\begin{array}{cccccc}1& 3& 6& 2& 5& 4\\ 3& 6& 1& 5& 2& 4\end{array}\right)=(136)(25)(4)=(136)(25).$

Переставка як добуток циклів

Нехай $\pi$ буде переставкою в $S$, і нехай

$S_1,\dots ,S_k\subset S,k\in \mathbb{N}$

будуть орбітами $\pi$ з кількістю елементів більшою ніж 1. Розглянемо елемент $S_j$, $j=1,\dots ,k$, нехай $n_j$ позначає потужність $S_j$,$|S_j|$ =$n_j$. Також, виберемо $a_{1,j}\in S_j$, і визначимо

$a_{i+1,j}=\pi (a_{i,j}),i\in \mathbb{N}.$

Тепер ми можемо виразити $\pi$ як добуток неперетинних циклів, as a product of disjoint cycles, а саме

$\pi =(a_{1,1}\dots a_{n_1,1})(a_{1,2}\dots a_{n_2,2})\dots (a_{1,k}\dots a_{n_k,k}).$

Зауважимо, що звична домовленість в циклічному записі визначає множення зліва направо (на відміну від композиції функцій, яка зазвичай виконується справа наліво). Наприклад, добуток $(12)(23)$ дорівнює $(132)$, але ні $(123)$.

Класи спряженості

Використаємо 24-елементну симетричну групу на $\{1,2,3,4\}$ виражену через використання циклічного запису, і груповану відповідно до класів спряженості:

$()$

$(12),(13),(14),(23),(24),(34)$ (транспозиції)

$(123),(132),(124),(142),(134),(143),(234),(243)$

$(12)(34),(13)(24),(14)(23)$

$(1234),(1243),(1324),(1342),(1423),(1432)$

Див. також

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

Джерела

• Шаблон:Вишенський.Перестюк.Комбінаторика
• Шаблон:PlanetMath
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.