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

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

В математиці, і зокрема в теорії груп, цикл — переставка елементів деякої множини 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, яка бієктивною функцією \sigma:X\to X, називається циклом, якщо дія на X підгрупи утвореної \sigma має саме одну орбіту з більш як одним елементом. Це поняття найчастіше вживають коли X скінченна множина; тоді й орбіта S скінченна. Нехай s_0 довільний елемент з S, і покладемо s_i=\sigma^i(s) \, для будь-якого i\in\mathbf{Z}. З того, що по припущенню S містить більше ніж один елемент, s_1\neq s_0; якщо S скінченна, існує мінімальне число k>1 для якого s_k=s_0. Тоді S=\{ s_0, s_1, \ldots, s_{k-1}\}, і \sigma є переставка визначена

\sigma(s_i) = s_{i+1} \quad\mbox{for }0\leq i<k

і \sigma(x)=x для будь-якого елементу з X\setminus S. Елементи не зафіксовані \sigma можна зобразити як

s_0\mapsto s_1\mapsto s_2\mapsto\cdots\mapsto s_{k-1}\mapsto s_k=s_0.

Цикл можна записати за допомогою циклічного запису \sigma = (s_0~s_1~\dots~s_{k-1}) (коми тут не вживаються з метою уникнення плутанини з k-кортежем). Довжина циклу — це кількість елементів його орбіти. Цикл довжини k також звуть k-цикл.

Основні властивості[ред.ред. код]

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

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

\binom nk(k-1)!=\frac{n(n-1)\cdots(n-k+1)}{k}=\frac{n!}{(n-k)!k}

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

Транспозиції[ред.ред. код]

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