Умножение перестановок, обратная перестановка, группа перестановок — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Группа перестановок)
(Источники и литература)
Строка 117: Строка 117:
  
 
=Источники и литература=
 
=Источники и литература=
* [http://ru.wikipedia.org/wiki/%D0%98%D0%BD%D0%B2%D0%BE%D0%BB%D1%8E%D1%86%D0%B8%D1%8F_(%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0)] - инволюция (Wikipedia, the free encyclopedia)
+
* [http://ru.wikipedia.org/wiki/%D0%98%D0%BD%D0%B2%D0%BE%D0%BB%D1%8E%D1%86%D0%B8%D1%8F_(%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0) инволюция (Wikipedia, the free encyclopedia)]
* Александров П.С. Лекции по аналитической геометрии, Стр.768, издательство "Наука", 1968 г.
+
* Н. И. Яцкин, Алгебра Теоремы и алгоритмы, Издательство «Ивановский государственный университет», 2006 г., стр. 161
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Комбинаторика]]
 
[[Категория: Комбинаторика]]

Версия 06:11, 3 декабря 2011

Умножение перестановок

Определение:
Умножением (композицией) перестановок называется перестановка, получающаяся по следующему правилу: [math] (a \circ b)_i = a_{b_i} [/math]


Утверждение:
Умножение перестановок ассоциативно: [math] (a \circ (b \circ c))_i = ((a \circ b) \circ c)_i [/math]
[math]\triangleright[/math]

Доказывается простым раскрытием скобок.

  1. [math] (a \circ (b \circ c))_i = a_{(b \circ c)_i} = a_{b_{c_i}} [/math]
  2. [math] ((a \circ b) \circ c)_i = (a \circ b)_{c_i} = a_{b_{c_i}} [/math]
[math]\triangleleft[/math]

Пример

[math] \varphi(1)=\begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 5 & 6 & 3 & 1 & 1 \end{bmatrix} [/math]

[math] \varphi(2)=\begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 1 & 3 & 6 & 5 & 2 \end{bmatrix} [/math]

[math] (\varphi(1) \circ \varphi(2))_i=[/math] [math] \begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 5 & 6 & 3 & 1 & 4 \end{bmatrix} \circ[/math] [math] \begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 1 & 3 & 6 & 5 & 2 \end{bmatrix} = \begin{bmatrix} 4 & 1 & 3 & 6 & 5 & 2 \\ 3 & 2 & 6 & 4 & 1 & 5 \end{bmatrix} \circ \begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 1 & 3 & 6 & 5 & 2 \end{bmatrix} =[/math] [math]\begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 2 & 6 & 4 & 1 & 5 \end{bmatrix}[/math]

Обратная перестановка

Определение:
Обратной перестановкой [math] a^{-1} [/math] к перестановке [math] a [/math] называется такая перестановка, что: [math] (a^{-1} \circ a)_i = (a \circ a^{-1})_i = i [/math]


Получение обратной перестановки

Пусть в массиве p[i] содержится перестановка, тогда в массиве op[i], после выполнения алгоритма, будет содержаться обратная перестановка.

for(i = 0; i < n; i++)
{
       for(j = 0; j < n; j++)
       {
           if(p[j] == i + 1) 
           {
               op[i] = j + 1;
           }
       }
}

При представлении перестановки в виде циклов обратную перестановку можно легко получить, инвертировав все ребра в циклах.

[math] a = (1, 3, 2), (4, 5) \Rightarrow a^{-1} = (1, 2, 3), (4, 5) [/math]

Инволюция

Определение:
Перестановка, равная своей обратной, называется инволюцией: [math] a_i = a^{-1}_i \Rightarrow (a \circ a ^{-1})_i = (a \circ a)_i = a_{a_i} = i [/math]


Утверждение:
Число инволюций можно посчитать, используя рекуррентную формулу: [math] a(n) = a(n-1) + (n-1)a(n-2),\ где a(0) = 1,\ a(1) = 1,\ n\gt 1.[/math]
[math]\triangleright[/math]

Доказательство:

Рассмотрим n-ый элемент перестановки. Возможны два случая, где он может находиться:

  1. n-ый элемент стоит на своём месте. Тогда оставшиеся [math]n-1[/math] элемент должны представлять собой инволюцию длины [math]n-1[/math], значит число таких перестановок равно [math]a (n-1)[/math]
  2. n-ый элемент стоит на некотором месте [math] k \ne \neq n [/math]. Тогда, чтобы перестановка была инволюцией, элемент k должен стоять на месте n. При этом остальные [math]n-2[/math] элемента также должны образовывать инволюцию длины [math]n-2[/math]. Получаем, что для фиксированного k существует [math]a (n-2)[/math] инволюций, но так как элемент k можно выбрать [math]n-1[/math] способом, то получается [math] (n-1) a (n-2) [/math] инволюций.
Таким образом, получаем формулу [math] a(n) = a(n-1) + (n-1)a(n-2)[/math]
[math]\triangleleft[/math]

Группа перестановок

Определение:
Пусть [math] M [/math] - множество, [math] M = \{ x, y, z, ... \} [/math], и на этом множестве задана бинарная операция [math] \circ [/math], такая, что для любого [math] x, y \in M: x \circ y = z \in M [/math].

Тогда группой называется алгебраическая структура, удовлетворяющая следующим свойствам:

  1. [math] (g_1 \circ g_2) \circ g_3 = g_1 \circ (g_2 \circ g_3) [/math] - ассоциативность соответствующей бинарной операции.
  2. Существование нейтрального элемента [math] e [/math] относительно операции [math] \circ [/math], такого, что для любого [math] g \in M: g \circ e = e \circ g = g [/math]
  3. Существование обратного элемента [math] g^{-1} [/math], такого, что для любого [math] g \in M [/math]существует [math] g^{-1} \in M: g \circ g^{-1} = g^{-1} \circ g = e [/math]


Утверждение:
Множество перестановок с [math] n [/math] элементами с операцией умножения является группой (часто группу перестановок называют симметрической, и обозначают [math] S_n [/math]).
[math]\triangleright[/math]
Свойства 1 и 3 доказаны выше, а в качестве нейтрального элемента выступает тождественная перестановка ([math] \pi_i = i [/math]).
[math]\triangleleft[/math]

Мощность множества симметрических групп: [math]\left\vert S_n \right\vert = n![/math]

Теорема Кэли утверждает, что любая конечная группа изоморфна подгруппе некоторой группе перестановок.

Источники и литература