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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Визначення[ред.ред. код]

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

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

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

Див. також[ред.ред. код]

Примітки[ред.ред. код]

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

Посилання[ред.ред. код]