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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Обратная перестановка)
(Обратная перестановка)
Строка 60: Строка 60:
 
<tex> a(n) = a(n-1) + (n-1)a(n-2),\ где a(0) = 1,\ a(1) = 1,\ n>1.</tex>
 
<tex> a(n) = a(n-1) + (n-1)a(n-2),\ где a(0) = 1,\ a(1) = 1,\ n>1.</tex>
  
Доказательство:
+
'''Доказательство:'''
  
Рассмотрим n-ый элемент перестановки. Есть два случая, где он может находиться:
+
Рассмотрим n-ый элемент перестановки. Возможны два случая, где он может находиться:
# n-ый элемент стоит на своём месте. Тогда относительно случая, когда элементов n-1 ничего не меняется, и число инволюций по-прежнему остаётся а(n-1)
+
# n-ый элемент стоит на своём месте. Тогда оставшиеся n-1 элемент должны представлять собой инволюцию длины n-1, значит число таких перестановок равно а(n-1)
# n-ый элемент стоит не на своём месте. Тогда вариантов мест на которых он может стоять будет n-1, и для каждого такого варианта мы получим возможное число инволюций а(n-2), так как тот элемент, на месте которого окажется n-ый элемент, сам переместится на место n-ого элемента.
+
# n-ый элемент стоит на некотором месте k!=n. Тогда, чтобы перестановка была инволюцией, элемент k должен стоять на месте n. При этом остальные n-2 элемента также должны образовывать инволюцию длины n-2. Получаем, что для фиксированного k существует а(n-2) инволюций, но так как элемент k можно выбрать n-1 способом, то получается (n-1)a(n-2) инволюций.
 +
 
 +
Таким образом, получаем формулу a(n)=a(n-1)+(n-1)a(n-2)
  
 
=Группа перестановок=
 
=Группа перестановок=

Версия 07:03, 26 ноября 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] a = {{1, 2, 3, 4, 5, 6} \choose {2, 5, 6, 3, 1, 4}}, b = {{1, 2, 3, 4, 5, 6} \choose {4, 1, 3, 6, 5, 2}} [/math]

[math] {{1, 2, 3, 4, 5, 6} \choose {2, 5, 6, 3, 1, 4}} \circ {{1, 2, 3, 4, 5, 6} \choose {4, 1, 3, 6, 5, 2}} = {{4, 1, 3, 6, 5, 2} \choose {3, 2, 6, 4, 1, 5}} \circ {{1, 2, 3, 4, 5, 6} \choose {4, 1, 3, 6, 5, 2}} = {{1, 2, 3, 4, 5, 6} \choose {3, 2, 6, 4, 1, 5}} [/math]

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

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


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

[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]

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

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

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

Таким образом, получаем формулу a(n)=a(n-1)+(n-1)a(n-2)

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

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

Пусть [math] M [/math] - множество, [math] M = \{ x, y, z, ... \} [/math], и на этом множестве задана бинарная операция [math] \circ [/math], такая, что [math] \forall 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] \forall g \in M: g \circ e = e \circ g = g [/math]
  3. Существование обратного элемента [math] g^{-1} [/math] : [math] \forall g \in M: \exists 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 выполняются уже по пунктам 1 и 2 выше, а в качестве нейтрального элемента можно брать тождественную перестановку ([math] \pi_i = i [/math]).
[math]\triangleleft[/math]

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