Відкрити головне меню

Цикл (математика)

перестановка, яка змінює елементи "по колу"
(Перенаправлено з Транспозиція (математика))

В математиці, і зокрема в теорії груп, цикл — перестановка елементів деякої множини X, яка відображає елементи деякої підмножини S в X один в інший циклічним чином, тоді як інші елементи X залишаються фіксованими. Наприклад, перестановка {1, 2, 3, 4}, що переставляє 1 в 3, 2 в 4, 3 в 2 і 4 в 1 є циклом, тоді як перестановка 1 в 3, 2 в 4, 3 в 1 і 4 в 2 ні (це окремі пари {1, 3} і {2, 4}). Множина S називається орбітою циклу.

ВизначенняРедагувати

Перестановка множини X, яка бієктивною функцією  , називається циклом, якщо дія на X підгрупи утвореної   має саме одну орбіту з більш як одним елементом. Це поняття найчастіше вживають коли X скінченна множина; тоді й орбіта S скінченна. Нехай   довільний елемент з S, і покладемо   для будь-якого  . З того, що по припущенню S містить більше ніж один елемент,  ; якщо S скінченна, існує мінімальне число   для якого  . Тоді  , і   є переставка визначена

 

і   для будь-якого елементу з  . Елементи не зафіксовані   можна зобразити як

 .

Цикл можна записати за допомогою циклічного запису   (коми тут не вживаються з метою уникнення плутанини з k-кортежем). Довжина циклу — це кількість елементів його орбіти. Цикл довжини k також звуть k-цикл.

Основні властивостіРедагувати

Один з головних вислідів у симетричних групах стверджує, що будь-яку перестановку можна виразити як добуток неперетинних циклів (точніше: циклів з неперетинними орбітами); такі цикли комутують між собою, і вираз перестановки унікальний з точністю до порядку циклів (але зверніть увагу, що циклічний запис не унікальний: кожен k-цикл сам по собі може бути представлений k різними способами, в залежності від вибору   в його орбіті). Отже мультимножина довжин циклів в цьому виразі унікально визначає перестановку, парність і клас спряженості перестановки в симетричній групі також визначаються цим.

Кількість k-циклів у симетричній групі Sn для   дається такими тотожними формулами

 

k-цикл має парність (−1)k − 1.

ТранспозиціїРедагувати

Цикл з лише двома елементами називається транспозицією. Наприклад перестановка {1, 4, 3, 2}, яка переводить 1 в 1, 2 в 4, 3 в 3 і 4 в 2 — це транспозиція (а саме така, що міняє місцями 2 і 4).