Действие перестановки на набор из элементов, представление в виде циклов — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 13: Строка 13:
  
 
Также, композицию перестановок можно выразить как действие одной перестановки на другую.
 
Также, композицию перестановок можно выразить как действие одной перестановки на другую.
 +
 +
Стоит отметить, что действие перестановки <tex>\pi^n</tex> соответствует переходу по графу <tex>n</tex> раз
  
 
==Циклы==
 
==Циклы==
Строка 19: Строка 21:
  
 
Перестановку можно представить в виде графа. Граф содержит ребро от вершины <tex>x_i</tex> к вершине <tex>x_j</tex> если <tex>\pi(x_i) = x_j</tex>. Тогда циклы перестановки соответствуют циклическим путям в графе.
 
Перестановку можно представить в виде графа. Граф содержит ребро от вершины <tex>x_i</tex> к вершине <tex>x_j</tex> если <tex>\pi(x_i) = x_j</tex>. Тогда циклы перестановки соответствуют циклическим путям в графе.
 +
 +
 +
 +
С циклами связаны некоторые интересные свойства перестановок.
 +
{{Определение
 +
|neat = 1
 +
|definition=Степенью перестановки называется минимальное число <tex>n \in N</tex> такое, что <tex>\pi^n = i</tex>}}
 +
 +
 +
 +
 +
 +
{{Утверждение
 +
|statement=
 +
Степень перестановки равна наименьшему общему кратному длин всех циклов
 +
}}
 +
Доказательство этого факта [[Вычисление_порядка_перестановки_в_группе_перестановок | здесь]]
 +
 +
 +
{{Утверждение
 +
|statement=
 +
Если длины всех циклов не превышают 2, то перестановка является [[Умножение_перестановок,_обратная_перестановка,_группа_перестановок#def_involution | инволюцией]].
 +
|proof=
 +
Действительно, в таком случае по вышеупомянутому <tex>\pi^2 = i</tex>. Домножив на <tex>\pi^{-1}</tex> получим <tex>\pi^{-1} = \pi</tex>.
 +
}}
 +
 +
== Источники ==
 +
 +
* [http://ru.wikipedia.org/wiki/%CF%E5%F0%E5%F1%F2%E0%ED%EE%E2%EA%E0 Википедия]
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
  
 
[[Категория: Комбинаторика ]]
 
[[Категория: Комбинаторика ]]

Версия 22:46, 11 января 2013

Действие перестановки на набор элементов

Определение:
Пусть [math]\pi[/math] — перестановка порядка [math]n[/math], и [math]\{a_i\}[/math] — множество некоторых объектов, занумерованных числами от одного до [math]n[/math]. Тогда результатом действия перестановки на этот набор объектов назовём множество объектов [math]\{b_i\}[/math], занумерованных числами от одного до [math]n[/math], причём [math]b_i = a_{\pi_i}[/math].


Иллюстрация действия перестановки

Обозначим за [math]A[/math] множество (не пронумерованных) объектов [math]\{a_1, \dots, a_n\}[/math]. Поскольку перестановку можно рассматривать как отображение [math]\pi \colon \{1, \dots, n\} \to \{1, \dots, n\}[/math], а нумерацию как отображение [math]\alpha \colon \{1, \dots, n\} \to A[/math], то действие перестановки можно определить как композицию отображений [math]\alpha \circ \pi[/math].

Например, рассмотрим множество [math]A = (a, b, c, d)[/math] и перестановку [math]\pi = \langle 3, 4, 1, 2 \rangle[/math]. Тогда результат действия [math]\pi[/math] на [math]A[/math] — упорядоченное множество [math]\pi(A) = (c, d, a, b)[/math]. Если рассмотреть граф перестановки (описано ниже), то действие перестановки можно представить таким образом: каждый элемент устанавливается в вершину графа, соответствующую номеру этого элемента, после чего каждый элемент передвигается по исходящему из этой вершины ребру.

Также, композицию перестановок можно выразить как действие одной перестановки на другую.

Стоит отметить, что действие перестановки [math]\pi^n[/math] соответствует переходу по графу [math]n[/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)=\langle 5,1,6,4,2,3\rangle [/math].

Перестановку можно представить в виде графа. Граф содержит ребро от вершины [math]x_i[/math] к вершине [math]x_j[/math] если [math]\pi(x_i) = x_j[/math]. Тогда циклы перестановки соответствуют циклическим путям в графе.


С циклами связаны некоторые интересные свойства перестановок.

Определение:
Степенью перестановки называется минимальное число [math]n \in N[/math] такое, что [math]\pi^n = i[/math]




Утверждение:
Степень перестановки равна наименьшему общему кратному длин всех циклов

Доказательство этого факта здесь


Утверждение:
Если длины всех циклов не превышают 2, то перестановка является инволюцией.
[math]\triangleright[/math]
Действительно, в таком случае по вышеупомянутому [math]\pi^2 = i[/math]. Домножив на [math]\pi^{-1}[/math] получим [math]\pi^{-1} = \pi[/math].
[math]\triangleleft[/math]

Источники