Циклическая перестановка

Тип (математической) перестановки без фиксированного элемента

В математике , и в частности в теории групп , циклическая перестановка — это перестановка, состоящая из одного цикла. ^{[1] [2]} В некоторых случаях циклические перестановки называются циклами ; ^[3] Если циклическая перестановка имеет k элементов, ее можно назвать k -циклом . Некоторые авторы расширяют это определение, включив в него перестановки с неподвижными точками в дополнение не более чем к одному нетривиальному циклу. ^{[3] [4]} В обозначениях циклов циклические перестановки обозначаются списком их элементов, заключенным в круглые скобки, в том порядке, в котором они переставляются.

Например, перестановка (1 3 2 4), которая отправляет 1 к 3, 3 к 2, 2 к 4 и 4 к 1, является 4-циклом, а перестановка (1 3 2)(4), которая отправляет 1 к 3 , 3–2, 2–1 и 4–4 некоторые авторы считают 3-циклом. С другой стороны, перестановка (1 3)(2 4), которая переводит 1 в 3, 3 в 1, 2 в 4 и 4 в 2, не является циклической перестановкой, поскольку она отдельно переставляет пары {1, 3} и { 2, 4}.

Множество элементов, не фиксируемых циклической перестановкой, называется орбитой циклической перестановки. ^{[ нужна цитата ]} Каждую перестановку на конечном числе элементов можно разложить на циклические перестановки на непересекающихся орбитах.

Отдельные циклические части перестановки также называются циклами , поэтому второй пример состоит из 3-цикла и 1-цикла (или фиксированной точки ), а третий состоит из двух 2-циклов.

Определение

Циклическая перестановка, состоящая из одного 8-цикла.

Не существует единого мнения относительно точного определения циклической перестановки. Некоторые авторы определяют перестановку σ множества X как циклическую, если «при последовательном применении каждый объект перестановленного набора будет последовательно проходить через позиции всех остальных объектов» ^[1] или, что то же самое, если ее представление в обозначениях цикла состоит одного цикла. ^[2] Другие дают более либеральное определение, допускающее фиксированные точки. ^{[3] [4]}

Непустое подмножество S множества X является циклом , если ограничение на S является циклической перестановкой S. Если X конечно , его циклы не пересекаются , а их объединение есть X. То есть они образуют разбиение , называемое циклическим разложением So. Согласно более разрешающему определению, перестановка X является циклической тогда и только тогда, когда X является ее уникальным циклом. ${\displaystyle \sigma }$ ${\displaystyle \sigma }$ ${\displaystyle \sigma .}$

Например, перестановка, записанная в циклической и двухстрочной записи (двумя способами) как

${\displaystyle {\begin{aligned}(1\ 4\ 6\ &8\ 3\ 7)(2)(5)\\&={\begin{pmatrix}1&2&3&4&5&6&7&8\\4&2&7&6&5&8&1&3\end{pmatrix}}\\&={\begin{pmatrix}1&4&6&8&3&7&2&5\\4&6&8&3&7&1&2&5\end{pmatrix}}\end{aligned}}}$

имеет один 6-цикл и два 1-цикла, диаграмма его цикла показана справа. Некоторые авторы считают эту перестановку циклической, другие - нет.

Перестановка, которая является циклической для расширенного определения, но не для ограниченного, с двумя фиксированными точками (1-циклами) и 6-циклом.

В расширенном определении существуют циклические перестановки, не состоящие из одного цикла.

Более формально, для расширенного определения, перестановка множества X , рассматриваемая как биективная функция , называется циклом, если действие на X подгруппы, порожденной, имеет не более одной орбиты с более чем одним элементом. ^[5] Это понятие чаще всего используется, когда X — конечное множество; тогда наибольшая орбита S также конечна. Позвольте быть любым элементом S и поставьте для любого . Если S конечно, существует минимальное число, для которого . Тогда , и является перестановкой, определяемой формулой ${\displaystyle \sigma }$ ${\displaystyle \sigma :X\to X}$ ${\displaystyle \sigma }$ ${\displaystyle s_{0}}$ ${\displaystyle s_{i}=\sigma ^{i}(s_{0})}$ ${\displaystyle i\in \mathbf {Z} }$ ${\displaystyle k\geq 1}$ ${\displaystyle s_{k}=s_{0}}$ ${\displaystyle S=\{s_{0},s_{1},\ldots ,s_{k-1}\}}$ ${\displaystyle \sigma }$

${\displaystyle \sigma (s_{i})=s_{i+1}}$для 0 ≤ я < к

и для любого элемента . Нефиксированные элементы можно представить как ${\displaystyle \sigma (x)=x}$ ${\displaystyle X\setminus S}$ ${\displaystyle \sigma }$

${\displaystyle s_{0}\mapsto s_{1}\mapsto s_{2}\mapsto \cdots \mapsto s_{k-1}\mapsto s_{k}=s_{0}}$.

Циклическую перестановку можно записать, используя обозначение компактного цикла (в этом обозначении между элементами нет запятых, чтобы избежать путаницы с k - кортежем ). Длина цикла равна числу элементов его наибольшей орбиты . Цикл длины k также называется k -циклом. ${\displaystyle \sigma =(s_{0}~s_{1}~\dots ~s_{k-1})}$

Орбита 1-цикла называется неподвижной точкой перестановки, но как перестановка каждый 1-цикл является тождественной перестановкой . ^[6] Когда используется обозначение цикла, 1-циклы часто опускаются, чтобы не возникло путаницы. ^[7]

Основные свойства

Один из основных результатов о симметричных группах состоит в том, что любую перестановку можно выразить как произведение непересекающихся циклов (точнее: циклов с непересекающимися орбитами); такие циклы коммутируют друг с другом, и выражение перестановки уникально с точностью до порядка циклов. ^{[a] Таким} образом, мультимножество длин циклов в этом выражении ( тип цикла ) однозначно определяется перестановкой, и ею определяются как сигнатура, так и класс сопряженности перестановки в симметричной группе. ^[8]

Число k -циклов в симметрической группе Sn определяется при , следующими эквивалентными формулами _: ${\displaystyle 1\leq k\leq n}$

$${\displaystyle {\binom {n}{k}}(k-1)!={\frac {n(n-1)\cdots (n-k+1)}{k}}={\frac {n!}{(n-k)!k}}.}$$

k -цикл имеет сигнатуру (−1) ^{k  − 1} .

Обратный цикл задается изменением порядка записей : . В частности, поскольку , каждый двухцикл является своим обратным. Поскольку непересекающиеся циклы коммутируют, обратное произведение непересекающихся циклов является результатом обращения каждого из циклов в отдельности. ${\displaystyle \sigma =(s_{0}~s_{1}~\dots ~s_{k-1})}$ ${\displaystyle \sigma ^{-1}=(s_{k-1}~\dots ~s_{1}~s_{0})}$ ${\displaystyle (a~b)=(b~a)}$

Транспозиции

Матрица _ ${\displaystyle \pi }$

Цикл, состоящий только из двух элементов, называется транспозицией . Например, перестановка , меняющая местами 2 и 4. Поскольку это 2-цикл, ее можно записать как . ${\displaystyle \pi ={\begin{pmatrix}1&2&3&4\\1&4&3&2\end{pmatrix}}}$ ${\displaystyle \pi =(2,4)}$

Характеристики

Любую перестановку можно выразить как композицию ( произведение ) транспозиций — формально они являются генераторами группы . ^[9] Фактически, когда перестановочный набор равен {1, 2, ..., n } для некоторого целого числа n , тогда любая перестановка может быть выражена как произведениесмежные транспозиции и так далее. Это следует из того, что произвольную транспозицию можно выразить как произведение соседних транспозиций. Конкретно, можно выразить транспозицию,перемещая k в l шаг за шагом, а затем перемещая l обратно туда, где было k , что меняет местами эти два и не вносит никаких других изменений: ${\displaystyle (1~2),(2~3),(3~4),}$ ${\displaystyle (k~~l)}$ ${\displaystyle k<l}$

${\displaystyle (k~~l)=(k~~k+1)\cdot (k+1~~k+2)\cdots (l-1~~l)\cdot (l-2~~l-1)\cdots (k~~k+1).}$

Разложение перестановки в произведение транспозиций получается, например, путем записи перестановки в виде произведения непересекающихся циклов, а затем итеративного разделения каждого из циклов длины 3 и длиннее на произведение транспозиции и цикла длины один. меньше:

${\displaystyle (a~b~c~d~\ldots ~y~z)=(a~b)\cdot (b~c~d~\ldots ~y~z).}$

Это означает, что первоначальный запрос состоит в том, чтобы перейти к to и, наконец , к . Вместо этого можно перекатывать элементы, сохраняя их положение, сначала выполнив правильный фактор (как обычно в операторной записи и следуя соглашению в статье « Перестановка »). Это переместилось в положение так, что после первой перестановки элементы и еще не заняли свои окончательные позиции. После этого выполняется транспозиция , затем адреса по индексу, чтобы поменять местами то, что было изначально , и ${\displaystyle a}$ ${\displaystyle b,}$ ${\displaystyle b}$ ${\displaystyle c,}$ ${\displaystyle y}$ ${\displaystyle z,}$ ${\displaystyle z}$ ${\displaystyle a.}$ ${\displaystyle a}$ ${\displaystyle z}$ ${\displaystyle b,}$ ${\displaystyle a}$ ${\displaystyle z}$ ${\displaystyle (a~b),}$ ${\displaystyle z}$ ${\displaystyle b}$ ${\displaystyle a}$ ${\displaystyle z.}$

Фактически, симметрическая группа является группой Кокстера , то есть она порождается элементами порядка 2 (смежными транспозициями), и все отношения имеют определенный вид.

Один из основных результатов о симметричных группах гласит, что либо все разложения данной перестановки в транспозиции имеют четное количество транспозиций, либо все они имеют нечетное количество транспозиций. ^[10] Это позволяет четности перестановки быть четко определенным понятием.

Смотрите также

• Циклическая сортировка - алгоритм сортировки, основанный на идее о том, что сортируемая перестановка может быть разбита на циклы, которые можно индивидуально вращать для получения отсортированного результата.
• Циклы и фиксированные точки
• Циклическая перестановка целого числа
• Обозначение цикла
• Круговая перестановка в белках
• Перетасовка Фишера-Йейтса

Примечания

1. Обратите внимание, что обозначение цикла не уникально: каждый k -цикл сам по себе может быть записан k разными способами, в зависимости от выбора на его орбите. ${\displaystyle s_{0}}$

Рекомендации

1. Гросс, Джонатан Л. (2008). Комбинаторные методы с компьютерными приложениями . Дискретная математика и ее приложения. Бока-Ратон, Флорида: Chapman & Hall/CRC. п. 29. ISBN 978-1-58488-743-0.
2. Кнут, Дональд Э. (2002). Искусство компьютерного программирования . Аддисон-Уэсли. п. 35.
3. Богарт, Кеннет П. (2000). Вводная комбинаторика (3-е изд.). Лондон: Harcourt Academic Press. п. 554. ИСБН 978-0-12-110830-4.
4. Розен, Кеннет Х. (2000). Справочник по дискретной и комбинаторной математике . Бока-Ратон, Лондон, Нью-Йорк: CRC press. ISBN 978-0-8493-0149-0.
5. Фрэли 1993, с. 103
6. Ротман 2006, с. 108
7. Саган 1991, с. 2
8. Ротман 2006, с. 117, 121
9. Ротман 2006, с. 118, п. 2.35.
10. Ротман 2006, с. 122

Источники

• Андерсон, Марлоу и Фейл, Тодд (2005), Первый курс абстрактной алгебры , Чепмен и Холл/CRC; 2-е издание. ISBN 1-58488-515-7 . 
• Фрели, Джон (1993), Первый курс абстрактной алгебры (5-е изд.), Аддисон Уэсли, ISBN 978-0-201-53467-2
• Ротман, Джозеф Дж. (2006), Первый курс абстрактной алгебры с приложениями (3-е изд.), Прентис-Холл, ISBN 978-0-13-186267-8
• Саган, Брюс Э. (1991), Симметричная группа / Представления, комбинаторные алгоритмы и симметричные функции , Уодсворт и Брукс / Коул, ISBN 978-0-534-15540-7

Внешние ссылки

В эту статью включены материалы из цикла PlanetMath , который доступен под лицензией Creative Commons Attribution/Share-Alike License .