Циклічний запис (англ. cycle notation ) — це угода щодо запису переставок у виразах циклів , що їх складають.[1] Також називають коловий запис (англ. circular notation ), а переставку — колова (циклічна ) переставка (англ. cyclic (circular) permutation ).[2]
Визначення
ред.
Нехай
S
{\displaystyle S}
буде скінченна множина , і
a
1
,
…
,
a
k
,
k
≥
2
{\displaystyle a_{1},\ldots ,a_{k},\quad k\geq 2}
будуть різними елементами в
S
{\displaystyle S}
. Вираз
(
a
1
…
a
k
)
{\displaystyle (a_{1}\ \ldots \ a_{k})}
позначає σ чиїми діями є
a
1
↦
a
2
↦
a
3
↦
…
↦
a
k
↦
a
1
.
{\displaystyle a_{1}\mapsto a_{2}\mapsto a_{3}\mapsto \ldots \mapsto a_{k}\mapsto a_{1}.}
Для кожного індексу i ,
σ
(
a
i
)
=
a
i
+
1
,
{\displaystyle \sigma (a_{i})=a_{i+1},}
де
a
k
+
1
{\displaystyle a_{k+1}}
означає
a
1
{\displaystyle a_{1}}
.
Існує
k
{\displaystyle k}
різних виразів для того самого циклу; всі наступні представляють один цикл:
(
a
1
a
2
a
3
…
a
k
)
=
(
a
2
a
3
…
a
k
a
1
)
=
⋯
=
(
a
k
a
1
a
2
…
a
k
−
1
)
.
{\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 \pi }
буде переставкою в
S
{\displaystyle S}
, і нехай
S
1
,
…
,
S
k
⊂
S
,
k
∈
N
{\displaystyle S_{1},\ldots ,S_{k}\subset S,\quad k\in \mathbb {N} }
будуть орбітами
π
{\displaystyle \pi }
з кількістю елементів більшою ніж 1. Розглянемо елемент
S
j
{\displaystyle S_{j}}
,
j
=
1
,
…
,
k
{\displaystyle j=1,\ldots ,k}
, нехай
n
j
{\displaystyle n_{j}}
позначає потужність
S
j
{\displaystyle S_{j}}
,
|
S
j
|
{\displaystyle |S_{j}|}
=
n
j
{\displaystyle n_{j}}
. Також, виберемо
a
1
,
j
∈
S
j
{\displaystyle a_{1,j}\in S_{j}}
, і визначимо
a
i
+
1
,
j
=
π
(
a
i
,
j
)
,
i
∈
N
.
{\displaystyle a_{i+1,j}=\pi (a_{i,j}),\quad i\in \mathbb {N} .\,}
Тепер ми можемо виразити
π
{\displaystyle \pi }
як добуток неперетинних циклів, as a product of disjoint cycles, а саме
π
=
(
a
1
,
1
…
a
n
1
,
1
)
(
a
1
,
2
…
a
n
2
,
2
)
…
(
a
1
,
k
…
a
n
k
,
k
)
.
{\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}).\,}
Зауважимо, що звична домовленість в циклічному записі визначає множення зліва направо (на відміну від композиції функцій , яка зазвичай виконується справа наліво). Наприклад, добуток
(
1
2
)
(
2
3
)
{\displaystyle (1\ 2)(2\ 3)}
дорівнює
(
1
3
2
)
{\displaystyle (1\ 3\ 2)}
, але ні
(
1
2
3
)
{\displaystyle (1\ 2\ 3)}
.
Використаємо 24-елементну симетричну групу на
{
1
,
2
,
3
,
4
}
{\displaystyle \{1,2,3,4\}}
виражену через використання циклічного запису, і груповану відповідно до класів спряженості :
(
)
{\displaystyle ()\,}
(
12
)
,
(
13
)
,
(
14
)
,
(
23
)
,
(
24
)
,
(
34
)
{\displaystyle (12),\;(13),\;(14),\;(23),\;(24),\;(34)}
(транспозиції )
(
123
)
,
(
132
)
,
(
124
)
,
(
142
)
,
(
134
)
,
(
143
)
,
(
234
)
,
(
243
)
{\displaystyle (123),\;(132),\;(124),\;(142),\;(134),\;(143),\;(234),\;(243)}
(
12
)
(
34
)
,
(
13
)
(
24
)
,
(
14
)
(
23
)
{\displaystyle (12)(34),\;(13)(24),\;(14)(23)}
(
1234
)
,
(
1243
)
,
(
1324
)
,
(
1342
)
,
(
1423
)
,
(
1432
)
{\displaystyle (1234),\;(1243),\;(1324),\;(1342),\;(1423),\;(1432)}
Див. також
ред.
Примітки
ред.
↑ Fraleigh 2002:89; Hungerford 1997:230
↑ Dehn 1930:19
↑ Hungerford 1997:231
↑ 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 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 .