Действие перестановки на набор из элементов, представление в виде циклов — различия между версиями
Tsarevfs (обсуждение | вклад) |
Tsarevfs (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
Индексы <math>i,j \in \mathcal{f}1, 2, \ldots, n\mathcal{g}</math>, где <math>n = \mathcal{j}X\mathcal{j}</math>. | Индексы <math>i,j \in \mathcal{f}1, 2, \ldots, n\mathcal{g}</math>, где <math>n = \mathcal{j}X\mathcal{j}</math>. | ||
Число <math>~n</math> называют порядком перестановки. Перестановку можно записать в виде упорядоченного набора из чисел <math>1, 2,\ldots, n</math>. | Число <math>~n</math> называют порядком перестановки. Перестановку можно записать в виде упорядоченного набора из чисел <math>1, 2,\ldots, n</math>. | ||
| − | Элемент такого набора <math>~<a_1,a_2,\ldots,a_n>~ a_k</math> означает, что <math>~\pi (x_{a_k}) = x_k </math>. Таким образом, если <math> \Theta = <x_1,x_{2},\ldots,x_{n}></math> — упорядоченный набор элементов из множества<math>~X</math>, то <math>\pi (<x_{1},x_{2},\ldots,x_{n}>) = <x_{q_1},x_{q_2},\ldots,x_{q_n}> </math>, где <math>q_{a_i} = i</math>. Например, применив перестановку <math>~<3,2,4,1> | + | Элемент такого набора <math>~<a_1,a_2,\ldots,a_n>~ a_k</math> означает, что <math>~\pi (x_{a_k}) = x_k </math>. Таким образом, если <math> \Theta = <x_1,x_{2},\ldots,x_{n}></math> — упорядоченный набор элементов из множества<math>~X</math>, то <math>\pi (<x_{1},x_{2},\ldots,x_{n}>) = <x_{q_1},x_{q_2},\ldots,x_{q_n}> </math>, где <math>q_{a_i} = i</math>. Например, применив перестановку <math>~<3,2,4,1></math> к набору элементов <math>~(x_1,x_2,x_3,x_4)</math>, получим набор <math>~<x_4,x_2,x_1,x_3></math>. <br\> |
==Произведение перестановок== | ==Произведение перестановок== | ||
Произведением перестановок <math>~\pi</math> и <math>~\sigma</math> называется композиция (т.е. последовательное применение) этих перестановок: <math>(\pi*\sigma)(\Theta) = \pi(\sigma(\Theta)) = \pi \circ \sigma (\Theta)</math>. | Произведением перестановок <math>~\pi</math> и <math>~\sigma</math> называется композиция (т.е. последовательное применение) этих перестановок: <math>(\pi*\sigma)(\Theta) = \pi(\sigma(\Theta)) = \pi \circ \sigma (\Theta)</math>. | ||
Легко показать, что произведение перестановок тоже является перестановкой, причем если <math>~\phi = \pi*\sigma</math>, то <math>\phi(x_i) = \pi \circ \sigma (x_i)</math>. | Легко показать, что произведение перестановок тоже является перестановкой, причем если <math>~\phi = \pi*\sigma</math>, то <math>\phi(x_i) = \pi \circ \sigma (x_i)</math>. | ||
==Циклы== | ==Циклы== | ||
| − | Циклом длины <math>~l</math> называется такая | + | Циклом длины <math>~l</math> называется такая перестановка <math>~\pi,</math> которая тождественна на всём множестве <math>X,</math> кроме подмножества <math>\{x_1,x_2,\dots,x_l\}\subset X</math> и <math>~\pi(x_l)=x_1,</math> <math>~\pi(x_i)=x_{i+1}.</math> Обозначается <math>(x_1,x_2,\dots,x_l).</math> Перестановку также можно записать в виде произведения непересекающихся циклов, причём единственным образом с точностью до порядка следования циклов в произведении. Например: <math>~(1, 5, 2)(3, 6)(4)=<5,1,6,4,2,3> </math>. |
| − | : <math>~(1, 5, 2)(3, 6)(4)=<5,1,6,4,2,3> </math>. Перестановку можно представить в виде графа. Граф содержит ребро от вершины <math>~x_i</math> к вершине <math>~x_j</math> если <math>~\pi(x_j) = x_i</math>, то есть элемент <math>~x_i</math> переходит в <math>~x_j</math> после применения перестановки <math>~\pi</math>. Тогда циклы перестановки соответствуют циклическим путям в графе. | + | |
| + | Перестановку можно представить в виде графа. Граф содержит ребро от вершины <math>~x_i</math> к вершине <math>~x_j</math> если <math>~\pi(x_j) = x_i</math>, то есть элемент <math>~x_i</math> переходит в <math>~x_j</math> после применения перестановки <math>~\pi</math>. Тогда циклы перестановки соответствуют циклическим путям в графе. | ||
[[Файл:Циклы_мал.png]] | [[Файл:Циклы_мал.png]] | ||
Версия 13:09, 10 декабря 2010
Перестановка — это отображение , которое каждому ставит во взаимно-однозначное соответствие
Индексы , где . Число называют порядком перестановки. Перестановку можно записать в виде упорядоченного набора из чисел . Элемент такого набора означает, что . Таким образом, если — упорядоченный набор элементов из множества, то , где . Например, применив перестановку к набору элементов , получим набор . <br\>
Произведение перестановок
Произведением перестановок и называется композиция (т.е. последовательное применение) этих перестановок: . Легко показать, что произведение перестановок тоже является перестановкой, причем если , то .
Циклы
Циклом длины называется такая перестановка которая тождественна на всём множестве кроме подмножества и Обозначается Перестановку также можно записать в виде произведения непересекающихся циклов, причём единственным образом с точностью до порядка следования циклов в произведении. Например: .
Перестановку можно представить в виде графа. Граф содержит ребро от вершины к вершине если , то есть элемент переходит в после применения перестановки . Тогда циклы перестановки соответствуют циклическим путям в графе.
