Изменения

Перейти к: навигация, поиск

Умножение перестановок, обратная перестановка, группа перестановок

5737 байт добавлено, 23:12, 9 января 2021
→‎Умножение перестановок
==Умножение перестановок==
{{Определение
|definition=
'''Умножением ''' (англ. ''multiplication'') или '''композицией''' (англ. ''composition'') перестановок , представленных в виде целочисленных функций <tex> a_i </tex>, где <tex>i - </tex> позиция элемента, а <tex> a_i </tex> — его номер, называется перестановка, получающаяся получаемая по следующему правилу:
<tex> (a \circ bab)_i = a_b_{b_ia_i} </tex>
}}
Умножение перестановок ассоциативно:
<tex> (a \circ (b \circ cbc))_i = ((a \circ bab) \circ c)_i </tex>
|proof=
Доказывается простым раскрытием скобок.
# <tex> (a \circ (b \circ cbc))_i = a_{(b \circ cbc)_i_{a_i} = a_c_{b_{c_ia_i}} </tex># <tex> ((a \circ bab) \circ c)_i = c_{(a \circ bab)_{c_i_i} = a_c_{b_{c_ia_i}} </tex>
}}
==Пример==Перед прочтением примера перемножения перестановок рекомендуем познакомиться с циклами в данной статье: [[Действие перестановки на набор из элементов, представление в виде циклов]]
<tex> \varphi(1)=\begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 5 & 6 & 3 & 1 & 1 \end{bmatrix} </tex> <tex> \varphi(2)=\begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 1 & 3 & 6 & 5 & 2 \end{bmatrix} </tex>=Пример===
<tex> (\varphi(1) \circ \varphi(2))_ia =</tex><tex> \begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & , 5 & , 6 & , 3 & 1 & 4 \end{bmatrix} \circ</tex> <tex> \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} =</tex><tex>\begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 2 & 6 & 4 & 1 & 5 \end{bmatrix}) </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} \circ a)_i = (a \circ aaa^{-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> a = (1, 3, 2), (4, 5) \Rightarrow a^{-1} = (1ая позиций в обратной перестановке, 2, 3), (4, 5) значение которой есть <tex> i </tex>
{{Определение
|id = def_involution
|definition=
Перестановка, равная своей обратной, называется '''инволюцией''' (англ. ''involution''):
<tex> a_i = a^{-1}_i \Rightarrow (a \circ a aa ^{-1})_i = (a \circ aaa)_i = a_{a_i} = i </tex>, то есть её представление в виде циклов не содержит цикла, размер которого больше двух.
}}
{{Утверждение
|statement=
Число инволюций можно посчитать, используя рекуррентную формулуКоличество инволюционных перестановок длины <tex>n\geqslant 2 </tex> может быть получено по формуле:<tex> aI(n) = aI(n-1) + (n-1)a\cdot I(n-2)</tex>,\ где a<tex> I(0) = 1,\ aI(1) = 1,\ n>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> }} {{Определение|definition= Перестановка, содержащая чётное количество инверсий, называется '''чётной''' (англ. ''even permutation''), в противном случае <tex> - </tex> '''нечётной''' (англ. ''odd permutation''). }} {{Определение|definition=
Рассмотрим n-ый элемент перестановки. Возможны Перестановка, меняющая местами только два случая, где он может находиться:# n-ый элемент стоит на своём месте. Тогда оставшиеся <tex>n-1</tex> элемент должны представлять собой инволюцию длины <tex>n-1</tex>элемента, значит число таких перестановок равно <tex>a называется '''транспозицией''' (n-1)</tex># n-ый элемент стоит на некотором месте <tex> k \ne \neq n </tex>англ. Тогда, чтобы перестановка была инволюцией, элемент k должен стоять на месте n. При этом остальные <tex>n-2</tex> элемента также должны образовывать инволюцию длины <tex>n-2</tex>. Получаем, что для фиксированного k существует <tex>a (n-2)</tex> инволюций, но так как элемент k можно выбрать <tex>n-1</tex> способом, то получается <tex> (n-1) a (n-2''transposition'') </tex> инволюций.
Таким образом, получаем формулу <tex> a(n) = a(n-1) + (n-1)a(n-2)</tex>
}}
{{Лемма|id=lemma1|statement=Получение обратной перестановки= Если в перестановке, длина которой больше <tex>1</tex>, поменять местами <tex> 2 </tex> элемента, то её четность изменится. |proof=
Для элементов, стоящих рядом, истинность утверждения очевидна: их взаимное расположение относительно других элементов не изменилось, а транспозиция этих чисел изменяет количество инверсий на единицу. Пусть в массиве p[i] содержится теперь между перемещаемыми элементами <tex> a </tex> и <tex> b </tex> находятся <tex> d </tex> элементов, то есть перестановкаимеет вид: <tex> \ldots </tex> , тогда в массиве op[i] <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(i = 0; i < n; i++) { for(j = 0; j < n; j++) { if(p[j] =Получение обратной перестановки== i + 1) { op[i] = j + 1; } } }
Пусть в массиве <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=
Пусть <tex> M </tex> - '''Группой''' (англ. ''group'') называется множество, <tex> M = \{ x, y, z, ... \} </tex>, и с заданной на этом множестве задана бинарная операция нём бинарной операцией <tex> \circ </tex>, такая, что <tex> : МM\forall x, y \in times M: x \circ y = z \in longrightarrow M </tex>., удовлетворяющей следующим свойствам:
Тогда группой называется алгебраическая структура# <tex> (g_1 \circ g_2) \circ g_3 = g_1 \circ (g_2 \circ g_3) </tex> — ассоциативность соответствующей бинарной операции.# Существование нейтрального элемента <tex> e </tex> относительно операции <tex> \circ </tex>, удовлетворяющая следующим свойствамтакого, что для любого <tex> g \in M: g \circ e = e \circ g = g </tex># Для любого <tex> g \in M </tex>существует <tex> g^{-1} \in M</tex> называемый обратным элементом, такой, что <tex>:g \circ g^{-1} = g^{-1} \circ g = e </tex>
# <tex> (g_1 \circ g_2) \circ g_3 = g_1 \circ (g_2 \circ g_3) </tex> - ассоциативность соответствующей бинарной операции.# Существование нейтрального элемента <tex> e </tex> относительно <tex> \circ </tex>: <tex> \forall g \in M: g \circ e = e \circ g = g </tex># Существование обратного элемента <tex> g^{-1} </tex> : <tex> \forall g \in M: \exists g^{-1} \in M: g \circ g^{-1} = g^{-1} \circ g = e </tex>
{{Утверждение
|statement=
Множество перестановок с <tex> n </tex> элементами с операцией умножения является группой (часто группу перестановок называют '''симметрической''' (англ. ''symmetric group''), и обозначают <tex> S_n </tex>).
|proof=
Свойства <tex>1</tex> и <tex>3</tex> (ассоциативность умножения и существование обратной перестановки для любой из перестановок) доказаны выше, а в качестве нейтрального элемента выступает тождественная перестановка (<tex> \pi_i = i </tex>).
}}
 
Мощность симметрической группы: <tex>\left\vert S_n \right\vert = n!</tex>
 
[[Теорема Кэли]] утверждает, что любая конечная группа изоморфна подгруппе некоторой группе перестановок.
 
==Группа чётных перестановок==
 
{{Определение
|definition=
'''Группа чётных перестановок''' (англ. ''alternating group'') <tex> A_n </tex> является подгруппой симметричной группы перестановок, образованной всеми чётными перестановками. Композиция не выводит из группы, так как если представить каждую перестановку группы в виде чётного числа транспозиций и перемножить их, чётность не изменится.
}}
{{Утверждение
|statement=
Множество Количество чётных перестановок с длины <tex> n </tex> элементами с операцией умножения является группой (часто группу перестановок называют симметрической, равно количеству нечётных и обозначают равно <tex> S_n \dfrac{n!}{2} </tex>).
|proof=
Свойства 1 и 3 доказаны вышеПусть число число чётных перестановок <tex> - </tex> <tex> a</tex>, а в качестве нейтрального элемента можно брать тождественную перестановку нечётных <tex> - </tex> <tex> b </tex>. Сделаем транспозицию <tex> (1, 2) </tex> для всех чётных перестановок. Получим <tex> a </tex> нечётных различных перестановок, то есть <tex> a\leqslant b </tex>. Проделаем то же самое с нечётными перестановками. Получим, что <tex> b\pi_i leqslant a </tex>, то есть <tex> a = i 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 \\mid S_n a_{k_1} & a_{k_2} & \mid = n!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]] утверждает, что любая конечная группа изоморфна подгруппе соответствующей группе перестановок.
=Источники и литература=
* [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 г.
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
Анонимный участник
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/13862...77171»

Навигация