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

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

Определение:

Пусть [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]A[/math] соответствует переходу элементов по развёрнутым рёбрам и даёт упорядоченное множество [math]b[/math], для которого верно [math]\pi(b) = i(A)[/math].

Утверждение:

Если [math]a = i(A), b = \pi^{-1}(A)[/math], то [math]\pi(b) = a[/math];

[math]\triangleright[/math]

Поскольку [math]b[/math] можно представить как [math]A \circ(\alpha \circ \pi^{-1})[/math], то [math]\pi(b) = (A \circ \alpha \circ \pi^{-1}) \circ \pi = A \circ \alpha \circ (\pi^{-1} \circ \pi) = A \circ \alpha = a [/math]

[math]\triangleleft[/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]

Утверждение:

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

[math]\triangleright[/math]

Пусть [math]k[/math] — степень перестановки. Граф перестановки разбит на циклы, и для того, чтобы какой-то элемент прошёл по своему циклу один раз, нужно возвести перестановку в степень [math]l[/math], где [math]l[/math] — длина цикла. Чтобы элемент прошёл цикл несколько раз и вернулся на своё место, перестановка должна быть возведена в степень кратную [math]l[/math]. Тогда только в том случае, когда [math]k[/math] делится на длины всех циклов, все элементы вернутся на свои места, а наименьшее такое [math]k[/math] — это НОК длин всех циклов.

[math]\triangleleft[/math]

Утверждение:

Если длины всех циклов не превышают 2, то перестановка является инволюцией.

[math]\triangleright[/math]

Действительно, в таком случае по вышеупомянутому [math]\pi^2 = i[/math]. Домножив на [math]\pi^{-1}[/math] получим [math]\pi^{-1} = \pi[/math].

[math]\triangleleft[/math]

Источники

• Википедия: Перестановки