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

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

Визначення

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

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

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

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

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

Нехай ${\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

Посилання

• Циклічний запис на PlanetMath.(англ.)
• Dehn, Edgar (1960) [1930], Algebraic Equations, Dover.
• Fraleigh, John (2003), A first course in abstract algebra (вид. 7th), Addison Wesley, с. 88–90, ISBN .
• Hungerford, Thomas W. (1997), Abstract Algebra: An Introduction, Brooks/Cole, ISBN .
• Johnson, James L. (2003), Probability and Statistics for Computer Science, Wiley Interscience, ISBN .