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

Циклічний запис (англ. 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\}$ виражену через використання циклічного запису, і груповану відповідно до класів спряженості:

$( )\,$

$(1 2), \;(1 3),\; (1 4),\; (2 3),\; (2 4),\; (3 4)$ (транспозиції)

$(1 2 3),\; (1 3 2),\; (1 2 4),\; (1 4 2),\; (1 3 4),\; (1 4 3),\; (2 3 4),\; (2 4 3)$

$(1 2)(3 4),\;(1 3)(2 4),\; (1 4)(2 3)$

$(1 2 3 4),\; (1 2 4 3),\; (1 3 2 4),\; (1 3 4 2),\; (1 4 2 3),\; (1 4 3 2)$

Див. також

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

Посилання

• Циклічний запис на PlanetMath.(англ.)
• Dehn, Edgar (1960) [1930], Algebraic Equations, Dover .
• Fraleigh, John (2003), A first course in abstract algebra (7th вид.), Addison Wesley, p. 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 .