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

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

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

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

Нехай буде скінченна множина, і

будуть різними елементами в . Вираз

позначає σ чиїми діями є

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

де означає .

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

1-елементний цикл на кшталт (3) — це тотожна переставка.[3] Тотожну переставку також можна записати як порожній цикл, "()".[4]

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

Нехай буде переставкою в , і нехай

будуть орбітами з кількістю елементів більшою ніж 1. Розглянемо елемент , , нехай позначає потужність , =. Також, виберемо , і визначимо

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

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

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

Використаємо 24-елементну симетричну групу на виражену через використання циклічного запису, і груповану відповідно до класів спряженості:

(транспозиції)

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

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

  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 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. .