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

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

.

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

Визначення

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

.

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

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

Вираз ${\displaystyle (a_{1}\ \ldots \ a_{k})}$ позначає σ чиїми діями є

${\displaystyle a_{1}\mapsto a_{2}\mapsto a_{3}\mapsto \ldots \mapsto a_{k}\mapsto a_{1}.}$

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

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

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

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

${\displaystyle (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) — це тотожна переставка.[3] Тотожну переставку також можна записати як порожній цикл, "()".[4]

Приклад

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

${\displaystyle \sigma ={\begin{pmatrix}1&2&3&4&5&6\\3&5&6&4&2&1\end{pmatrix}}={\begin{pmatrix}1&3&6&2&5&4\\3&6&1&5&2&4\end{pmatrix}}=(136)(25)(4)=(136)(25).}$

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

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

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

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

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

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

${\displaystyle \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}).\,}$

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

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

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

${\displaystyle ()\,}$

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

${\displaystyle (123),\;(132),\;(124),\;(142),\;(134),\;(143),\;(234),\;(243)}$

${\displaystyle (12)(34),\;(13)(24),\;(14)(23)}$

${\displaystyle (1234),\;(1243),\;(1324),\;(1342),\;(1423),\;(1432)}$

Див. також

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

Примітки

1. Fraleigh 2002:89; Hungerford 1997:230
2. Dehn 1930:19
3. Hungerford 1997:231
4. Johnson 2003:691

Джерела

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