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

Циклічний запис (англ. cycle notation) — це угода щодо запису переставок у виразах циклів, що їх складають. Також називають коловий запис (англ. circular notation), а переставку — колова (циклічна) переставка (англ. cyclic (circular) permutation).

Визначення

Нехай $S$ буде скінченна множина, і

$a_{1},\ldots ,a_{k},\quad k\geq 2$

будуть різними елементами в $S$. Вираз

$(a_{1}\ \ldots \ a_{k})$

позначає σ чиїми діями є

$a_{1}\mapsto a_{2}\mapsto a_{3}\mapsto \ldots \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}\ \ldots \ a_{k})=(a_{2}\ a_{3}\ \ldots \ a_{k}\ a_{1})=\cdots =(a_{k}\ a_{1}\ a_{2}\ \ldots \ a_{k-1}).\,$

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

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

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

$S_{1},\ldots ,S_{k}\subset S,\quad k\in \mathbb {N}$

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

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

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

$\pi =(a_{1,1}\ \ldots a_{n_{1},1})(a_{1,2}\ \ldots \ a_{n_{2},2})\ldots (a_{1,k}\ \ldots \ a_{n_{k},k}).\,$

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

Приклад

Використаємо 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.(англ.)
• Dehn, Edgar (1960) [1930], Algebraic Equations, Dover.
• Fraleigh, John (2003), A first course in abstract algebra (вид. 7th), Addison Wesley, с. 88–90, ISBN 978-0201763904.
• Hungerford, Thomas W. (1997), Abstract Algebra: An Introduction, Brooks/Cole, ISBN 978-0030105593.
• Johnson, James L. (2003), Probability and Statistics for Computer Science, Wiley Interscience, ISBN 978-0471326724.