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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Группа перестановок)
(Умножение перестановок)
(не показано 25 промежуточных версий 9 участников)
Строка 1: Строка 1:
=Умножение перестановок=
+
==Умножение перестановок==
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Умножением (композицией) перестановок называется перестановка, получающаяся по следующему правилу:
+
'''Умножением''' (англ. ''multiplication'') или '''композицией''' (англ. ''composition'') перестановок, представленных в виде целочисленных функций <tex> a_i </tex>, где <tex>i - </tex> позиция элемента, а <tex> a_i </tex> — его номер, называется перестановка, получаемая по следующему правилу:
  
<tex> (a \circ b)_i = a_{b_i} </tex>
+
<tex> (ab)_i = b_{a_i} </tex>
  
 
}}
 
}}
Строка 13: Строка 13:
 
Умножение перестановок ассоциативно:
 
Умножение перестановок ассоциативно:
  
<tex> (a \circ (b \circ c))_i = ((a \circ b) \circ c)_i </tex>
+
<tex> (a(bc))_i = ((ab)c)_i </tex>
  
 
|proof=
 
|proof=
Строка 19: Строка 19:
 
Доказывается простым раскрытием скобок.
 
Доказывается простым раскрытием скобок.
  
# <tex> (a \circ (b \circ c))_i = a_{(b \circ c)_i} = a_{b_{c_i}} </tex>
+
# <tex> (a(bc))_i = (bc)_{a_i} = c_{b_{a_i}} </tex>
# <tex> ((a \circ b) \circ c)_i = (a \circ b)_{c_i} = a_{b_{c_i}} </tex>
+
# <tex> ((ab)c)_i = c_{(ab)_i} = c_{b_{a_i}} </tex>
  
 
}}
 
}}
  
==Пример==
+
Перед прочтением примера перемножения перестановок рекомендуем познакомиться с циклами в данной статье: [[Действие перестановки на набор из элементов, представление в виде циклов]]
  
<tex> \varphi(1)=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 5 & 6 & 3 & 1 & 1 \end{pmatrix} </tex> 
+
===Пример===
   
 
<tex> \varphi(2)=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 1 & 3 & 6 & 5 & 2 \end{pmatrix} </tex>
 
  
<tex> (\varphi(1) \circ \varphi(2))_i=</tex>
+
<tex> a = {2, 5, 6, 3, 1, 4} = (1, 2, 5)(3, 6, 4) </tex>
<tex> \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 5 & 6 & 3 & 1 & 4 \end{pmatrix} \circ</tex> 
 
<tex> \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 1 & 3 & 6 & 5 & 2 \end{pmatrix} =  
 
\begin{pmatrix} 4 & 1 & 3 & 6 & 5 & 2 \\ 3 & 2 & 6 & 4 & 1 & 5 \end{pmatrix} \circ
 
\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 1 & 3 & 6 & 5 & 2 \end{pmatrix} =</tex>
 
<tex>\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 2 & 6 & 4 & 1 & 5 \end{pmatrix}</tex>
 
  
=Обратная перестановка=
+
<tex> b = {4, 1, 3, 6, 5, 2} = (1, 4, 6, 2) </tex>
 +
 
 +
<tex> ab = {a_4, a_1, a_3, a_6, a_5, a_2} = {3, 2, 6, 4, 1, 5} </tex>
 +
 
 +
или
 +
 
 +
<tex> ab = (1, 2, 5)(3, 6, 4)(1, 4, 6, 5) = (1, 3, 6, 5)(2)(4) = (1, 3, 6, 5) </tex>
 +
 
 +
==Обратная перестановка==
 +
 
 +
{{Определение
 +
|definition=
 +
 
 +
'''Обратной перестановкой''' (англ. ''inverse permutation'') <tex> a^{-1} </tex> к перестановке <tex> a </tex> называется такая перестановка, что:
 +
 
 +
<tex> (a^{-1}a)_i = (aa^{-1})_i = i </tex>
 +
 
 +
}}
 +
 
 +
{{Утверждение
 +
|statement=
 +
Для каждой перестановки существует перестановка, обратная ей.
 +
|proof=
 +
Пусть дана перестановка <tex> a </tex>, построим обратную ей перестановку <tex> a^{-1}</tex>: если <tex> a_x = y </tex>, то <tex> a^{-1}_y = x </tex>. Очевидно, что данная перестановка является обратной к <tex> a </tex>.
 +
 
 +
}}
 +
 
 +
Также обратная перестановка единственна. Это следует из того, что для каждой <tex> i </tex>-ой позиций в исходной перестановке однозначно определяется <tex> j </tex>-ая позиций в обратной перестановке, значение которой есть <tex> i </tex>
  
 
{{Определение
 
{{Определение
 +
|id = def_involution
 
|definition=
 
|definition=
 +
Перестановка, равная своей обратной, называется '''инволюцией''' (англ. ''involution''):
 +
 +
<tex> a_i = a^{-1}_i \Rightarrow (aa ^{-1})_i = (aa)_i = a_{a_i} = i </tex>, то есть её представление в виде циклов не содержит цикла, размер которого больше двух.
 +
 +
}}
 +
 +
{{Утверждение
 +
|statement=
 +
Количество инволюционных перестановок длины <tex>n\geqslant 2 </tex> может быть получено по формуле: <tex> I(n) = I(n-1)+(n-1)\cdot I(n-2) </tex>, где <tex> I(0) = I(1) = 1. </tex>
 +
|proof=
 +
Докажем формулу по '''индукции'''. '''Базой''' являются <tex> I(0) = I(1) = 1 </tex>. '''Предположим''', что для всех <tex> I(i) </tex>, где <tex> i < n</tex>, <tex> n > 1 </tex>, формула верна. Рассмотрим перестановку длины <tex> n </tex> и попробуем найти количество инволюций этой длины. Существует <tex> I(n-1)</tex> инволюций, при <tex>a_n = n </tex> (у которых последний элемент представляет собой цикл длины <tex> 1 </tex>), а число инволюций длины <tex> n </tex>, содержащих в своём представлении в виде циклов цикл <tex>(j,n)</tex>, где <tex> 1\leqslant j\leqslant n-1 </tex>, <tex> (n-1)\cdot I(n-2)</tex> (так как при фиксированных <tex> j </tex> и <tex> n </tex> имеем <tex> I(n-2) </tex> перестановок оставшихся элементов, которые не нарушают свойств инволюции). Таким образом, <tex> I(n) = I(n-1)+(n-1)\cdot I(n-2). </tex>
  
Обратной перестановкой <tex> a^{-1} </tex> к перестановке <tex> a </tex> называется такая перестановка, что:
+
}}
 +
 
 +
{{Определение
 +
|definition=
  
<tex> (a^{-1} \circ a)_i = (a \circ a^{-1})_i = i </tex>
+
Перестановка, содержащая чётное количество инверсий, называется '''чётной''' (англ. ''even permutation''), в противном случае <tex> - </tex> '''нечётной''' (англ. ''odd permutation'').
  
 
}}
 
}}
Строка 50: Строка 85:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Перестановка, равная своей обратной, называется инволюцией:
 
  
<tex> a_i = a^{-1}_i \Rightarrow (a \circ a ^{-1})_i = (a \circ a)_i = a_{a_i} = i </tex>
+
Перестановка, меняющая местами только два элемента, называется '''транспозицией''' (англ. ''transposition'').
  
 
}}
 
}}
  
==Получение обратной перестановки==
+
{{Лемма|id=lemma1
 +
|statement=
 +
 
 +
Если в перестановке, длина которой больше <tex>1</tex>, поменять местами <tex> 2 </tex> элемента, то её четность изменится.
  
Пусть в массиве p[i] содержится перестановка, тогда в массиве op[i], после выполнения алгоритма, будет содержаться обратная перестановка.
+
|proof=
  
  for(i = 0; i < n; i++)
+
Для элементов, стоящих рядом, истинность утверждения очевидна: их взаимное расположение относительно других элементов не изменилось, а транспозиция этих чисел изменяет количество инверсий на единицу. Пусть теперь между перемещаемыми элементами <tex> a </tex> и <tex> b </tex> находятся <tex> d </tex> элементов, то есть перестановка имеет вид:  <tex>  \ldots </tex>    ,    <tex> a, s_1, s_2, \ldots, s_d, b, \ldots </tex>. Сначала поменяем последовательно <tex> a </tex> с числами <tex> s_1, s_2, \ldots, s_d, b </tex>, а затем число <tex>b</tex> с рядом стоящими <tex> s_d, s_d-1, \ldots, s_1 </tex>. В итоге мы выполним <tex> 2\cdot d + 1 </tex> транспозиций рядом стоящих элементов, то есть чётность перестановки изменится.
  {
+
}}
        for(j = 0; j < n; j++)
 
        {
 
            if(p[j] == i + 1)
 
            {
 
                op[i] = j + 1;
 
            }
 
        }
 
}
 
  
При представлении перестановки в виде циклов обратную перестановку можно легко получить, инвертировав все ребра в циклах.
+
===Получение обратной перестановки===
  
<tex> a = (1, 3, 2), (4, 5) \Rightarrow a^{-1} = (1, 2, 3), (4, 5) </tex>
+
Пусть в массиве <tex> p </tex> содержится перестановка, длины <tex> n </tex>, тогда после выполнения алгоритма в массиве <tex> rep </tex> будет содержаться перестановка, обратная ей.
 +
'''fun''' reversePerm(p : '''int[]''', rep : '''int[]''')
 +
  '''for''' i = 1 '''to''' n
 +
      rep[p[i]] = i;
  
=Группа перестановок=
+
==Группа перестановок==
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Группой называется множество <tex> M </tex> с заданной на нём бинарной операцией <tex> \circ: МM\times M \longrightarrow M</tex>, удовлетворяющей следующим свойствам:
+
'''Группой''' (англ. ''group'') называется множество <tex> M </tex> с заданной на нём бинарной операцией <tex> \circ: МM\times M \longrightarrow M</tex>, удовлетворяющей следующим свойствам:
  
 
# <tex> (g_1 \circ g_2) \circ g_3 = g_1 \circ (g_2 \circ g_3) </tex> — ассоциативность соответствующей бинарной операции.
 
# <tex> (g_1 \circ g_2) \circ g_3 = g_1 \circ (g_2 \circ g_3) </tex> — ассоциативность соответствующей бинарной операции.
Строка 89: Строка 121:
 
{{Утверждение
 
{{Утверждение
 
|statement=
 
|statement=
Множество перестановок с <tex> n </tex> элементами с операцией умножения является группой (часто группу перестановок называют симметрической, и обозначают <tex> S_n </tex>).
+
Множество перестановок с <tex> n </tex> элементами с операцией умножения является группой (часто группу перестановок называют '''симметрической''' (англ. ''symmetric group''), и обозначают <tex> S_n </tex>).
 
|proof=
 
|proof=
Свойства 1 и 3 доказаны выше, а в качестве нейтрального элемента выступает тождественная перестановка (<tex> \pi_i = i </tex>).  
+
Свойства <tex>1</tex> и <tex>3</tex> (ассоциативность умножения и существование обратной перестановки для любой из перестановок) доказаны выше, а в качестве нейтрального элемента выступает тождественная перестановка (<tex> \pi_i = i </tex>).  
 
}}
 
}}
  
Строка 98: Строка 130:
 
[[Теорема Кэли]] утверждает, что любая конечная группа изоморфна подгруппе некоторой группе перестановок.
 
[[Теорема Кэли]] утверждает, что любая конечная группа изоморфна подгруппе некоторой группе перестановок.
  
=Источники и литература=
+
==Группа чётных перестановок==
* [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)]
+
 
* Н. И. Яцкин, Алгебра Теоремы и алгоритмы, Издательство «Ивановский государственный университет», 2006 г., стр. 161
+
{{Определение
 +
|definition=
 +
'''Группа чётных перестановок''' (англ. ''alternating group'') <tex> A_n </tex> является подгруппой симметричной группы перестановок, образованной всеми чётными перестановками. Композиция не выводит из группы, так как если представить каждую перестановку группы в виде чётного числа транспозиций и перемножить их, чётность не изменится.
 +
}}
 +
 
 +
{{Утверждение
 +
|statement=
 +
Количество чётных перестановок длины <tex> n </tex> равно количеству нечётных и равно <tex> \dfrac{n!}{2} </tex>
 +
|proof=
 +
Пусть число число чётных перестановок  <tex> - </tex>  <tex> a</tex>, а нечётных <tex> - </tex>  <tex> b </tex>. Сделаем транспозицию <tex> (1, 2) </tex> для всех чётных перестановок. Получим <tex> a </tex> нечётных различных перестановок, то есть <tex> a\leqslant b </tex>. Проделаем то же самое с нечётными перестановками. Получим, что <tex> b\leqslant a </tex>, то есть <tex> a = b </tex> и <tex> a = \dfrac{n!}{2} </tex>.
 +
}}
 +
 
 +
==Группа подстановок==
 +
 
 +
{{Определение
 +
|definition=
 +
'''Подстановкой''' (англ. ''substitution'') называется всякое взаимно однозначное отображение <tex> A </tex> множества первых <tex>n</tex> натуральных чисел на себя. 
 +
 
 +
}}
 +
 
 +
Всякая подстановка <tex>A</tex> может быть записана при помощи двух перестановок, подписанных одна под другой:
 +
 
 +
<tex> A = \begin{pmatrix} q_1 & q_2 & \ldots & q_n \\ a_{k_1} & a_{k_2} & \ldots & a_{k_n} \end{pmatrix} </tex>
 +
 
 +
Где через <tex> a_{k_i} </tex> обозначается то число, в которое при подстановке <tex> A </tex> переходит число <tex> q_i </tex>.
 +
 
 +
{{Определение
 +
|definition=
 +
'''Группой подстановок''' (англ. ''group of substitutions'') называется некоторая совокупность подстановок, замкнутая относительно композиции отображений, определяющей бинарную операцию для подстановок на одном и том же множестве.
 +
 
 +
}}
 +
 
 +
==См. также==
 +
*[[Теорема Кэли]]
 +
*[[Действие перестановки на набор из элементов, представление в виде циклов]]
 +
 
 +
==Источники информации==
 +
* [https://en.wikipedia.org/wiki/Involution_(mathematics) Wikipedia {{---}} Involution]
 +
 
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Комбинаторика]]
 
[[Категория: Комбинаторика]]

Версия 23:12, 9 января 2021

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

Определение:
Умножением (англ. multiplication) или композицией (англ. composition) перестановок, представленных в виде целочисленных функций [math] a_i [/math], где [math]i - [/math] позиция элемента, а [math] a_i [/math] — его номер, называется перестановка, получаемая по следующему правилу: [math] (ab)_i = b_{a_i} [/math]


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

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

  1. [math] (a(bc))_i = (bc)_{a_i} = c_{b_{a_i}} [/math]
  2. [math] ((ab)c)_i = c_{(ab)_i} = c_{b_{a_i}} [/math]
[math]\triangleleft[/math]

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

Пример

[math] a = {2, 5, 6, 3, 1, 4} = (1, 2, 5)(3, 6, 4) [/math]

[math] b = {4, 1, 3, 6, 5, 2} = (1, 4, 6, 2) [/math]

[math] ab = {a_4, a_1, a_3, a_6, a_5, a_2} = {3, 2, 6, 4, 1, 5} [/math]

или

[math] ab = (1, 2, 5)(3, 6, 4)(1, 4, 6, 5) = (1, 3, 6, 5)(2)(4) = (1, 3, 6, 5) [/math]

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

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


Утверждение:
Для каждой перестановки существует перестановка, обратная ей.
[math]\triangleright[/math]
Пусть дана перестановка [math] a [/math], построим обратную ей перестановку [math] a^{-1}[/math]: если [math] a_x = y [/math], то [math] a^{-1}_y = x [/math]. Очевидно, что данная перестановка является обратной к [math] a [/math].
[math]\triangleleft[/math]

Также обратная перестановка единственна. Это следует из того, что для каждой [math] i [/math]-ой позиций в исходной перестановке однозначно определяется [math] j [/math]-ая позиций в обратной перестановке, значение которой есть [math] i [/math]


Определение:
Перестановка, равная своей обратной, называется инволюцией (англ. involution): [math] a_i = a^{-1}_i \Rightarrow (aa ^{-1})_i = (aa)_i = a_{a_i} = i [/math], то есть её представление в виде циклов не содержит цикла, размер которого больше двух.


Утверждение:
Количество инволюционных перестановок длины [math]n\geqslant 2 [/math] может быть получено по формуле: [math] I(n) = I(n-1)+(n-1)\cdot I(n-2) [/math], где [math] I(0) = I(1) = 1. [/math]
[math]\triangleright[/math]
Докажем формулу по индукции. Базой являются [math] I(0) = I(1) = 1 [/math]. Предположим, что для всех [math] I(i) [/math], где [math] i \lt n[/math], [math] n \gt 1 [/math], формула верна. Рассмотрим перестановку длины [math] n [/math] и попробуем найти количество инволюций этой длины. Существует [math] I(n-1)[/math] инволюций, при [math]a_n = n [/math] (у которых последний элемент представляет собой цикл длины [math] 1 [/math]), а число инволюций длины [math] n [/math], содержащих в своём представлении в виде циклов цикл [math](j,n)[/math], где [math] 1\leqslant j\leqslant n-1 [/math], [math] (n-1)\cdot I(n-2)[/math] (так как при фиксированных [math] j [/math] и [math] n [/math] имеем [math] I(n-2) [/math] перестановок оставшихся элементов, которые не нарушают свойств инволюции). Таким образом, [math] I(n) = I(n-1)+(n-1)\cdot I(n-2). [/math]
[math]\triangleleft[/math]


Определение:
Перестановка, содержащая чётное количество инверсий, называется чётной (англ. even permutation), в противном случае [math] - [/math] нечётной (англ. odd permutation).


Определение:
Перестановка, меняющая местами только два элемента, называется транспозицией (англ. transposition).


Лемма:
Если в перестановке, длина которой больше [math]1[/math], поменять местами [math] 2 [/math] элемента, то её четность изменится.
Доказательство:
[math]\triangleright[/math]
Для элементов, стоящих рядом, истинность утверждения очевидна: их взаимное расположение относительно других элементов не изменилось, а транспозиция этих чисел изменяет количество инверсий на единицу. Пусть теперь между перемещаемыми элементами [math] a [/math] и [math] b [/math] находятся [math] d [/math] элементов, то есть перестановка имеет вид: [math] \ldots [/math] , [math] a, s_1, s_2, \ldots, s_d, b, \ldots [/math]. Сначала поменяем последовательно [math] a [/math] с числами [math] s_1, s_2, \ldots, s_d, b [/math], а затем число [math]b[/math] с рядом стоящими [math] s_d, s_d-1, \ldots, s_1 [/math]. В итоге мы выполним [math] 2\cdot d + 1 [/math] транспозиций рядом стоящих элементов, то есть чётность перестановки изменится.
[math]\triangleleft[/math]

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

Пусть в массиве [math] p [/math] содержится перестановка, длины [math] n [/math], тогда после выполнения алгоритма в массиве [math] rep [/math] будет содержаться перестановка, обратная ей.

fun reversePerm(p : int[], rep : int[])
  for i = 1 to n
      rep[p[i]] = i;

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

Определение:
Группой (англ. group) называется множество [math] M [/math] с заданной на нём бинарной операцией [math] \circ: МM\times M \longrightarrow 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 \in M [/math]существует [math] g^{-1} \in M[/math] называемый обратным элементом, такой, что [math]: g \circ g^{-1} = g^{-1} \circ g = e [/math]


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

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

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

Группа чётных перестановок

Определение:
Группа чётных перестановок (англ. alternating group) [math] A_n [/math] является подгруппой симметричной группы перестановок, образованной всеми чётными перестановками. Композиция не выводит из группы, так как если представить каждую перестановку группы в виде чётного числа транспозиций и перемножить их, чётность не изменится.


Утверждение:
Количество чётных перестановок длины [math] n [/math] равно количеству нечётных и равно [math] \dfrac{n!}{2} [/math]
[math]\triangleright[/math]
Пусть число число чётных перестановок [math] - [/math] [math] a[/math], а нечётных [math] - [/math] [math] b [/math]. Сделаем транспозицию [math] (1, 2) [/math] для всех чётных перестановок. Получим [math] a [/math] нечётных различных перестановок, то есть [math] a\leqslant b [/math]. Проделаем то же самое с нечётными перестановками. Получим, что [math] b\leqslant a [/math], то есть [math] a = b [/math] и [math] a = \dfrac{n!}{2} [/math].
[math]\triangleleft[/math]

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

Определение:
Подстановкой (англ. substitution) называется всякое взаимно однозначное отображение [math] A [/math] множества первых [math]n[/math] натуральных чисел на себя.


Всякая подстановка [math]A[/math] может быть записана при помощи двух перестановок, подписанных одна под другой:

[math] A = \begin{pmatrix} q_1 & q_2 & \ldots & q_n \\ a_{k_1} & a_{k_2} & \ldots & a_{k_n} \end{pmatrix} [/math]

Где через [math] a_{k_i} [/math] обозначается то число, в которое при подстановке [math] A [/math] переходит число [math] q_i [/math].


Определение:
Группой подстановок (англ. group of substitutions) называется некоторая совокупность подстановок, замкнутая относительно композиции отображений, определяющей бинарную операцию для подстановок на одном и том же множестве.


См. также

Источники информации