Викиконспекты - Вклад участника [ru]

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

2018-01-18T06:25:44Z

Denis: Небольшие фиксы

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

{{Определение
|definition=
'''Умножением''' (англ. ''multiplication'') или '''композицией''' (англ. ''composition'') перестановок, представленных в виде целочисленных функций <tex> a_i </tex>, где <tex>i - </tex> позиция элемента, а <tex> a_i </tex> — его номер, называется перестановка, получаемая по следующему правилу:

<tex> (ab)_i = a_{b_i} </tex>

}}

Иногда применяется обратная формулировка, то есть: <tex> (ab)_i = b_{a_i} </tex>

{{Утверждение
|statement=
Умножение перестановок ассоциативно:

<tex> (a(bc))_i = ((ab)c)_i </tex>

|proof=

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

# <tex> (a(bc))_i = a_{(bc)_i} = a_{b_{c_i}} </tex>
# <tex> ((ab)c)_i = (ab)_{c_i} = a_{b_{c_i}} </tex>

}}

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

===Пример===

<tex> a = {2, 5, 6, 3, 1, 4} = (1, 2, 5)(3, 6, 4) </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=
Перестановка, равная своей обратной, называется '''инволюцией''' (англ. ''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>

}}

{{Определение
|definition=

Перестановка, содержащая чётное количество инверсий, называется '''чётной''' (англ. ''even permutation''), в противном случае <tex> - </tex> '''нечётной''' (англ. ''odd permutation'').

}}

{{Определение
|definition=

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

}}

{{Лемма|id=lemma1
|statement=

Если в перестановке, длина которой больше <tex>1</tex>, поменять местами <tex> 2 </tex> элемента, то её четность изменится.

|proof=

Для элементов, стоящих рядом, истинность утверждения очевидна: их взаимное расположение относительно других элементов не изменилось, а транспозиция этих чисел изменяет количество инверсий на единицу. Пусть теперь между перемещаемыми элементами <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> транспозиций рядом стоящих элементов, то есть чётность перестановки изменится.
}}

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

Пусть в массиве <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=
'''Группой''' (англ. ''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> 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>

}}

{{Утверждение
|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> \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]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

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

2018-01-13T18:47:27Z

Denis:

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

{{Определение
|definition=
'''Умножением''' (англ. ''multiplication'') или '''композицией''' (англ. ''composition'') перестановок,представленных в виде целочисленных функций <tex> a_i </tex>, где <tex>i - </tex> позиция элемента, а <tex> a_i </tex> — его номер, называется перестановка, получаемая по следующему правилу:

<tex> (ab)_i = a_{b_i} </tex>

}}

{{Утверждение
|statement=
Умножение перестановок ассоциативно:

<tex> (a(bc))_i = ((ab)c)_i </tex>

|proof=

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

# <tex> (a(bc))_i = a_{(bc)_i} = a_{b_{c_i}} </tex>
# <tex> ((ab)c)_i = (ab)_{c_i} = a_{b_{c_i}} </tex>

}}

===Пример===

<tex> a = {2, 5, 6, 3, 1, 4} = (1, 2, 5)(3, 6, 4) </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=

'''Обратной перестановкой''' (англ. ''an 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>.

}}

{{Определение
|id = def_involution
|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>

}}

{{Определение
|definition=

Перестановка, содержащая чётное количество инверсий, называется '''чётной''' (англ. ''even permutation''), в противном случае <tex> - </tex> '''нечётной''' (англ. ''odd permutation'').

}}

{{Определение
|definition=

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

}}

{{Лемма|id=lemma1
|statement=

Если в перестановке, длина которой больше <tex>1</tex>, поменять местами <tex> 2 </tex> элемента, то её четность изменится.

|proof=

Для элементов, стоящих рядом, истинность утверждения очевидна: их взаимное расположение относительно других элементов не изменилось, а транспозиция этих чисел изменяет количество инверсий на единицу. Пусть теперь между перемещаемыми элементами <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> транспозиций рядом стоящих элементов, то есть чётность перестановки изменится.
}}

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

Пусть в массиве <tex>p[i]</tex> содержится перестановка, тогда в массиве <tex>rep[i]</tex>, после выполнения алгоритма, будет содержаться обратная перестановка.
'''fun''' reversePerm(p : '''int[]''', rep : '''int[]''')
'''int''' n = p.size;
'''for''' i = 0 '''to''' n
'''for''' j = 0 '''to''' n
'''if''' p[j] == i + 1
rep[i] = j + 1;

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

<tex> a = (1, 3, 2), (4, 5) \Rightarrow a^{-1} = (1, 2, 3), (4, 5) </tex>

Отсюда следует более эффективный алгоритм, где <tex> visited[] </tex> - массив посещённых элементов:
'''fun''' reversePerm (visited : '''boolean[]''', p : '''int[]''', rep : '''int[]''')
'''int''' n = p.size;
'''for''' i = 0 '''to''' n
'''if''' visited[i]
'''continue''';
''// инвертировать цикл, начинающийся в позиции <tex> i </tex> ''
'''int''' last = i;
'''int''' j = p[i];
'''while''' '''true'''
'''int''' next = p[j];
p[j] = last;
visited[j] = '''true''';
'''if''' j == i
'''break''';
last = j;
j = next;

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

{{Определение
|definition=
'''Группой''' (англ. ''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> 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>

}}

{{Утверждение
|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> \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]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

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

2018-01-13T18:45:56Z

Denis:

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

{{Определение
|definition=
'''Умножением''' (англ. ''multiplication'') или '''композицией''' (англ. ''composition'') перестановок,представленных в виде целочисленных функций <tex> a_i </tex>, где <tex>i - </tex> позиция элемента, а <tex> a_i </tex> — его номер, называется перестановка, получаемая по следующему правилу:

<tex> (ab)_i = a_{b_i} </tex>

}}

{{Утверждение
|statement=
Умножение перестановок ассоциативно:

<tex> (a(bc))_i = ((ab)c)_i </tex>

|proof=

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

# <tex> (a(bc))_i = a_{(bc)_i} = a_{b_{c_i}} </tex>
# <tex> ((ab)c)_i = (ab)_{c_i} = a_{b_{c_i}} </tex>

}}

===Пример===

<tex> a = {2, 5, 6, 3, 1, 4} = (1, 2, 5)(3, 6, 4) </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=

'''Обратной перестановкой''' (англ. ''an 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>.

}}

{{Определение
|id = def_involution
|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>

}}

{{Определение
|definition=

Перестановка, содержащая чётное количество инверсий, называется '''чётной''' (англ. ''even permutation''), в противном случае <tex> - </tex> '''нечётной''' (англ. ''odd permutation'').

}}

{{Определение
|definition=

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

}}

{{Лемма|id=lemma1
|statement=

Если в перестановке, длина которой больше <tex>1</tex>, поменять местами <tex> 2 </tex> элемента, то её четность изменится.

|proof=

Для элементов, стоящих рядом, истинность утверждения очевидна: их взаимное расположение относительно других элементов не изменилось, а транспозиция этих чисел изменяет количество инверсий на единицу. Пусть теперь между перемещаемыми элементами <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> транспозиций рядом стоящих элементов, то есть чётность перестановки изменится.
}}

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

Пусть в массиве <tex>p[i]</tex> содержится перестановка, тогда в массиве <tex>rep[i]</tex>, после выполнения алгоритма, будет содержаться обратная перестановка.
'''fun''' reversePerm(p : '''int[]''', rep : '''int[]''')
'''int''' n = p.size;
'''for''' i = 0 '''to''' n
'''for''' j = 0 '''to''' n
'''if''' p[j] == i + 1
rep[i] = j + 1;

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

<tex> a = (1, 3, 2), (4, 5) \Rightarrow a^{-1} = (1, 2, 3), (4, 5) </tex>

Отсюда следует более эффективный алгоритм, где <tex> visited[] </tex> - массив посещённых элементов:
'''fun''' reversePerm (visited : '''boolean[]''', p : '''int[]''', rep : '''int[]''')
'''int''' n = p.size;
'''for''' i = 0 '''to''' n
'''if''' visited[i]
'''continue''';
''// инвертировать цикл, начинающийся в позиции <tex> i </tex> ''
'''int''' last = i;
'''int''' j = p[i];
'''while''' '''true'''
'''int''' next = p[j];
p[j] = last;
visited[j] = '''true''';
'''if''' j == i
'''break''';
last = j;
j = next;

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

{{Определение
|definition=
'''Группой''' (англ. ''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> 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>

}}

{{Утверждение
|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> \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'') называется некоторая совокупность подстановок, замкнутая относительно композиции отображений, определяющей бинарную операцию для подстановок на одном и том же множестве.

}}

==См. также==
*[[Теорема Кэли]]
*[[Действие перестановки на набор из элементов, представление в виде циклов]]

<references />

==Источники и литература==
* [https://en.wikipedia.org/wiki/Involution_(mathematics) Wikipedia {{---}} Involution]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

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

2018-01-13T18:42:49Z

Denis: Fixed links and proof

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

{{Определение
|definition=
'''Умножением''' (англ. ''multiplication'') или '''композицией''' (англ. ''composition'') перестановок,представленных в виде целочисленных функций <tex> a_i </tex>, где <tex>i - </tex> позиция элемента, а <tex> a_i </tex> — его номер, называется перестановка, получаемая по следующему правилу:

<tex> (ab)_i = a_{b_i} </tex>

}}

{{Утверждение
|statement=
Умножение перестановок ассоциативно:

<tex> (a(bc))_i = ((ab)c)_i </tex>

|proof=

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

# <tex> (a(bc))_i = a_{(bc)_i} = a_{b_{c_i}} </tex>
# <tex> ((ab)c)_i = (ab)_{c_i} = a_{b_{c_i}} </tex>

}}

===Пример===

<tex> a = {2, 5, 6, 3, 1, 4} = (1, 2, 5)(3, 6, 4) </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=

'''Обратной перестановкой''' (англ. ''an 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>.

}}

{{Определение
|id = def_involution
|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>

}}

{{Определение
|definition=

Перестановка, содержащая чётное количество инверсий, называется '''чётной''' (англ. ''even permutation''), в противном случае <tex> - </tex> '''нечётной''' (англ. ''odd permutation'').

}}

{{Определение
|definition=

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

}}

{{Лемма|id=lemma1
|statement=

Если в перестановке, длина которой больше <tex>1</tex>, поменять местами <tex> 2 </tex> элемента, то её четность изменится.

|proof=

Для элементов, стоящих рядом, истинность утверждения очевидна: их взаимное расположение относительно других элементов не изменилось, а транспозиция этих чисел изменяет количество инверсий на единицу. Пусть теперь между перемещаемыми элементами <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> транспозиций рядом стоящих элементов, то есть чётность перестановки изменится.
}}

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

Пусть в массиве <tex>p[i]</tex> содержится перестановка, тогда в массиве <tex>rep[i]</tex>, после выполнения алгоритма, будет содержаться обратная перестановка.
'''fun''' reversePerm(p : '''int[]''', rep : '''int[]''')
'''int''' n = p.size;
'''for''' i = 0 '''to''' n
'''for''' j = 0 '''to''' n
'''if''' p[j] == i + 1
rep[i] = j + 1;

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

<tex> a = (1, 3, 2), (4, 5) \Rightarrow a^{-1} = (1, 2, 3), (4, 5) </tex>

Отсюда следует более эффективный алгоритм, где <tex> visited[] </tex> - массив посещённых элементов:
'''fun''' reversePerm (visited : '''boolean[]''', p : '''int[]''', rep : '''int[]''')
'''int''' n = p.size;
'''for''' i = 0 '''to''' n
'''if''' visited[i]
'''continue''';
''// инвертировать цикл, начинающийся в позиции <tex> i </tex> ''
'''int''' last = i;
'''int''' j = p[i];
'''while''' '''true'''
'''int''' next = p[j];
p[j] = last;
visited[j] = '''true''';
'''if''' j == i
'''break''';
last = j;
j = next;

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

{{Определение
|definition=
'''Группой''' (англ. ''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> 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>

}}

{{Утверждение
|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> \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'') называется некоторая совокупность подстановок, замкнутая относительно композиции отображений, определяющей бинарную операцию для подстановок на одном и том же множестве.

}}

==См. также==
*[[Теорема Кэли]]
*[[Действие перестановки на набор из элементов, представление в виде циклов]]

<references />

==Источники и литература==
* [https://en.wikipedia.org/wiki/Involution_(mathematics) Wikipedia - Involution]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

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

2018-01-11T23:13:50Z

Denis: Изменено доказательство инволюций

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

{{Определение
|definition=
'''Умножением''' (англ. ''multiplication'') или '''композицией''' (англ. ''composition'') перестановок,представленных в виде целочисленных функций <tex> a_i </tex>, где <tex>i - </tex> позиция элемента, а <tex> a_i </tex> — его номер, называется перестановка, получаемая по следующему правилу:

<tex> (ab)_i = a_{b_i} </tex>

}}

{{Утверждение
|statement=
Умножение перестановок ассоциативно:

<tex> (a(bc))_i = ((ab)c)_i </tex>

|proof=

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

# <tex> (a(bc))_i = a_{(bc)_i} = a_{b_{c_i}} </tex>
# <tex> ((ab)c)_i = (ab)_{c_i} = a_{b_{c_i}} </tex>

}}

===Пример===

<tex> a = {2, 5, 6, 3, 1, 4} = (1, 2, 5)(3, 6, 4) </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=

'''Обратной перестановкой''' (англ. ''an 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>.

}}

{{Определение
|id = def_involution
|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> i < n </tex> и <tex> n > 1 </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=

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

}}

{{Лемма|id=lemma1
|statement=

Если в перестановке, длина которой больше <tex>1</tex>, поменять местами <tex> 2 </tex> элемента, то её четность изменится.

|proof=

Для элементов, стоящих рядом, истинность утверждения очевидна: их взаимное расположение относительно других элементов не изменилось, а транспозиция этих чисел изменяет количество инверсий на единицу. Пусть теперь между перемещаемыми элементами <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> транспозиций рядом стоящих элементов, то есть чётность перестановки изменится.
}}

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

Пусть в массиве <tex>p[i]</tex> содержится перестановка, тогда в массиве <tex>rep[i]</tex>, после выполнения алгоритма, будет содержаться обратная перестановка.
'''fun''' reversePerm(p : '''int[]''', rep : '''int[]''')
'''int''' n = p.size;
'''for''' i = 0 '''to''' n
'''for''' j = 0 '''to''' n
'''if''' p[j] == i + 1
rep[i] = j + 1;

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

<tex> a = (1, 3, 2), (4, 5) \Rightarrow a^{-1} = (1, 2, 3), (4, 5) </tex>

Отсюда следует более эффективный алгоритм, где <tex> visited[] </tex> - массив посещённых элементов:
'''fun''' reversePerm (visited : '''boolean[]''', p : '''int[]''', rep : '''int[]''')
'''int''' n = p.size;
'''for''' i = 0 '''to''' n
'''if''' visited[i]
'''continue''';
''// инвертировать цикл, начинающийся в позиции <tex> i </tex> ''
'''int''' last = i;
'''int''' j = p[i];
'''while''' '''true'''
'''int''' next = p[j];
p[j] = last;
visited[j] = '''true''';
'''if''' j == i
'''break''';
last = j;
j = next;

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

{{Определение
|definition=
'''Группой''' (англ. ''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> 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>

}}

{{Утверждение
|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> \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)
* Н. И. Яцкин, Алгебра Теоремы и алгоритмы, Издательство «Ивановский государственный университет», 2006 г., стр. 161

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

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

2018-01-06T12:48:15Z

Denis: Добавлено доказательство существования обратной перестановки для любой перестановки и указание на прувы свойств группы перестановок

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

{{Определение
|definition=
'''Умножением''' (англ. ''multiplication'') или '''композицией''' (англ. ''composition'') перестановок,представленных в виде целочисленных функций <tex> a_i </tex>, где <tex>i - </tex> позиция элемента, а <tex> a_i </tex> — его номер, называется перестановка, получаемая по следующему правилу:

<tex> (ab)_i = a_{b_i} </tex>

}}

{{Утверждение
|statement=
Умножение перестановок ассоциативно:

<tex> (a(bc))_i = ((ab)c)_i </tex>

|proof=

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

# <tex> (a(bc))_i = a_{(bc)_i} = a_{b_{c_i}} </tex>
# <tex> ((ab)c)_i = (ab)_{c_i} = a_{b_{c_i}} </tex>

}}

===Пример===

<tex> a = {2, 5, 6, 3, 1, 4} = (1, 2, 5)(3, 6, 4) </tex>

<tex> b = {4, 1, 3, 6, 5, 2} = (1, 4, 6, 5) </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=

'''Обратной перестановкой''' (англ. ''an 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>.

}}

{{Определение
|id = def_involution
|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 < n </tex> перестановок, при <tex> n > 1 </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=

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

}}

{{Лемма|id=lemma1
|statement=

Если в перестановке, длина которой больше <tex>1</tex>, поменять местами <tex> 2 </tex> элемента, то её четность изменится.

|proof=

Для элементов, стоящих рядом, истинность утверждения очевидна: их взаимное расположение относительно других элементов не изменилось, а транспозиция этих чисел изменяет количество инверсий на единицу. Пусть теперь между перемещаемыми элементами <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> транспозиций рядом стоящих элементов, то есть чётность перестановки изменится.
}}

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

Пусть в массиве <tex>p[i]</tex> содержится перестановка, тогда в массиве <tex>rep[i]</tex>, после выполнения алгоритма, будет содержаться обратная перестановка.
'''fun''' reversePerm(p : '''int[]''', rep : '''int[]''')
'''int''' n = p.size;
'''for''' i = 0 '''to''' n
'''for''' j = 0 '''to''' n
'''if''' p[j] == i + 1
rep[i] = j + 1;

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

<tex> a = (1, 3, 2), (4, 5) \Rightarrow a^{-1} = (1, 2, 3), (4, 5) </tex>

Отсюда следует более эффективный алгоритм, где <tex> visited[] </tex> - массив посещённых элементов:
'''fun''' reversePerm (visited : '''boolean[]''', p : '''int[]''', rep : '''int[]''')
'''int''' n = p.size;
'''for''' i = 0 '''to''' n
'''if''' visited[i]
'''continue''';
''// инвертировать цикл, начинающийся в позиции <tex> i </tex> ''
'''int''' last = i;
'''int''' j = p[i];
'''while''' '''true'''
'''int''' next = p[j];
p[j] = last;
visited[j] = '''true''';
'''if''' j == i
'''break''';
last = j;
j = next;

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

{{Определение
|definition=
'''Группой''' (англ. ''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> 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>

}}

{{Утверждение
|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> \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)
* Н. И. Яцкин, Алгебра Теоремы и алгоритмы, Издательство «Ивановский государственный университет», 2006 г., стр. 161

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

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

2018-01-06T06:30:22Z

Denis:

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

{{Определение
|definition=
'''Умножением''' (англ. ''multiplication'') или '''композицией''' (англ. ''composition'') перестановок,представленных в виде целочисленных функций <tex> a_i </tex>, где <tex>i - </tex> позиция элемента, а <tex> a_i </tex> — его номер, называется перестановка, получаемая по следующему правилу:

<tex> (ab)_i = a_{b_i} </tex>

}}

{{Утверждение
|statement=
Умножение перестановок ассоциативно:

<tex> (a(bc))_i = ((ab)c)_i </tex>

|proof=

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

# <tex> (a(bc))_i = a_{(bc)_i} = a_{b_{c_i}} </tex>
# <tex> ((ab)c)_i = (ab)_{c_i} = a_{b_{c_i}} </tex>

}}

===Пример===

<tex> a = {2, 5, 6, 3, 1, 4} = (1, 2, 5)(3, 6, 4) </tex>

<tex> b = {4, 1, 3, 6, 5, 2} = (1, 4, 6, 5) </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=

'''Обратной перестановкой''' (англ. ''an inverse permutation'') <tex> a^{-1} </tex> к перестановке <tex> a </tex> называется такая перестановка, что:

<tex> (a^{-1}a)_i = (aa^{-1})_i = i </tex>

}}

{{Определение
|id = def_involution
|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 < n </tex> перестановок, при <tex> n > 1 </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=

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

}}

{{Лемма|id=lemma1
|statement=

Если в перестановке, длина которой больше <tex>1</tex>, поменять местами <tex> 2 </tex> элемента, то её четность изменится.

|proof=

Для элементов, стоящих рядом, истинность утверждения очевидна: их взаимное расположение относительно других элементов не изменилось, а транспозиция этих чисел изменяет количество инверсий на единицу. Пусть теперь между перемещаемыми элементами <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> транспозиций рядом стоящих элементов, то есть чётность перестановки изменится.
}}

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

Пусть в массиве <tex>p[i]</tex> содержится перестановка, тогда в массиве <tex>rep[i]</tex>, после выполнения алгоритма, будет содержаться обратная перестановка.
'''fun''' reversePerm(p : '''int[]''', rep : '''int[]''')
'''int''' n = p.size;
'''for''' i = 0 '''to''' n
'''for''' j = 0 '''to''' n
'''if''' p[j] == i + 1
rep[i] = j + 1;

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

<tex> a = (1, 3, 2), (4, 5) \Rightarrow a^{-1} = (1, 2, 3), (4, 5) </tex>

Отсюда следует более эффективный алгоритм, где <tex> visited[] </tex> - массив посещённых элементов:
'''fun''' reversePerm (visited : '''boolean[]''', p : '''int[]''', rep : '''int[]''')
'''int''' n = p.size;
'''for''' i = 0 '''to''' n
'''if''' visited[i]
'''continue''';
''// инвертировать цикл, начинающийся в позиции <tex> i </tex> ''
'''int''' last = i;
'''int''' j = p[i];
'''while''' '''true'''
'''int''' next = p[j];
p[j] = last;
visited[j] = '''true''';
'''if''' j == i
'''break''';
last = j;
j = next;

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

{{Определение
|definition=
'''Группой''' (англ. ''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> 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>

}}

{{Утверждение
|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> \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)
* Н. И. Яцкин, Алгебра Теоремы и алгоритмы, Издательство «Ивановский государственный университет», 2006 г., стр. 161

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

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

2018-01-06T04:52:15Z

Denis: Уточнено док-во инволюций + мелкие фиксы

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

{{Определение
|definition=
'''Умножением''' (англ. ''multiplication'') или '''композицией''' (англ. ''composition'') перестановок,представленных в виде целочисленных функций <tex> a_i </tex>, где <tex>i - </tex> позиция элемента, а <tex> a_i </tex> — его номер, называется перестановка, получаемая по следующему правилу:

<tex> (ab)_i = a_{b_i} </tex>

}}

{{Утверждение
|statement=
Умножение перестановок ассоциативно:

<tex> (a(bc))_i = ((ab)c)_i </tex>

|proof=

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

# <tex> (a(bc))_i = a_{(bc)_i} = a_{b_{c_i}} </tex>
# <tex> ((ab)c)_i = (ab)_{c_i} = a_{b_{c_i}} </tex>

}}

===Пример===

<tex> a = {2, 5, 6, 3, 1, 4} = (1, 2, 5)(3, 6, 4) </tex>

<tex> b = {4, 1, 3, 6, 5, 2} = (1, 4, 6, 5) </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=

'''Обратной перестановкой''' (англ. ''an inverse permutation'') <tex> a^{-1} </tex> к перестановке <tex> a </tex> называется такая перестановка, что:

<tex> (a^{-1}a)_i = (aa^{-1})_i = i </tex>

}}

{{Определение
|id = def_involution
|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 < n </tex> перестановок, при <tex> n > 1 </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=

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

}}

{{Лемма|id=lemma1
|statement=

Если в перестановке, длина которой больше <tex>1</tex>, поменять местами <tex> 2 </tex> элемента, то её четность изменится.

|proof=

Для элементов, стоящих рядом, истинность утверждения очевидна: их взаимное расположение относительно других элементов не изменилось, а транспозиция этих чисел изменяет количество инверсий на единицу. Пусть теперь между перемещаемыми элементами <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> транспозиций рядом стоящих элементов, то есть чётность перестановки изменится.
}}

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

Пусть в массиве <tex>p[i]</tex> содержится перестановка, тогда в массиве <tex>rep[i]</tex>, после выполнения алгоритма, будет содержаться обратная перестановка.
'''fun''' reversePerm(p : '''int[]''', rep : '''int[]''')
'''int''' n = p.size;
'''for''' i = 0 '''to''' n
'''for''' j = 0 '''to''' n
'''if''' p[j] == i + 1
rep[i] = j + 1;

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

<tex> a = (1, 3, 2), (4, 5) \Rightarrow a^{-1} = (1, 2, 3), (4, 5) </tex>

Отсюда следует более эффективный алгоритм, где <tex> visited[] </tex> - массив посещённых элементов:
'''fun''' reversePerm (visited : '''boolean[]''', p : '''int[]''', rep : '''int[]''')
'''int''' n = p.size;
'''for''' i = 0 '''to''' n
'''if''' visited[i]
'''continue''';
''// инвертировать цикл, начинающийся в позиции <tex> i </tex> ''
'''int''' last = i;
'''int''' j = p[i];
'''while''' '''true'''
'''int''' next = p[j];
p[j] = last;
visited[j] = '''true''';
'''if''' j == i
'''break''';
last = j;
j = next;

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

{{Определение
|definition=
'''Группой''' (англ. ''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> 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>

}}

{{Утверждение
|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> \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)
* Н. И. Яцкин, Алгебра Теоремы и алгоритмы, Издательство «Ивановский государственный университет», 2006 г., стр. 161

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

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

2018-01-05T09:49:13Z

Denis:

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

{{Определение
|definition=
'''Умножением''' (англ. ''multiplication'') или '''композицией''' (англ. ''composition'') перестановок,представленных в виде целочисленных функций <tex> a_i </tex>, где <tex>i - </tex> позиция элемента, а <tex> a_i </tex> — его номер, называется перестановка, получаемая по следующему правилу:

<tex> (ab)_i = a_{b_i} </tex>

}}

{{Утверждение
|statement=
Умножение перестановок ассоциативно:

<tex> (a(bc))_i = ((ab)c)_i </tex>

|proof=

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

# <tex> (a(bc))_i = a_{(bc)_i} = a_{b_{c_i}} </tex>
# <tex> ((ab)c)_i = (ab)_{c_i} = a_{b_{c_i}} </tex>

}}

===Пример===

<tex> a = {2, 5, 6, 3, 1, 4} = (1, 2, 5)(3, 6, 4) </tex>

<tex> b = {4, 1, 3, 6, 5, 2} = (1, 4, 6, 5) </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=

'''Обратной перестановкой''' (англ. ''an inverse permutation'') <tex> a^{-1} </tex> к перестановке <tex> a </tex> называется такая перестановка, что:

<tex> (a^{-1}a)_i = (aa^{-1})_i = i </tex>

}}

{{Определение
|id = def_involution
|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(n-1)</tex> инволюций, при <tex>a_n = n </tex>. Число инволюций, содержащих цикл <tex>(j,n)</tex>, где <tex> 1\leq j\leq n-1 </tex>, <tex> (n-1)\cdot I(n-2)</tex>. Имеем, что <tex> I(n) = I(n-1)+(n-1)\cdot I(n-2). </tex>

}}

{{Определение
|definition=

Перестановка, содержащая чётное количество инверсий, называется '''чётной''', в противном случае <tex> - </tex> '''нечётной'''.

}}

{{Определение
|definition=

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

}}

{{Лемма|id=lemma1
|statement=

Если в перестановке, длина которой больше <tex>1</tex>, поменять местами <tex> 2 </tex> элемента, то её четность изменится.

|proof=

Для элементов, стоящих рядом, истинность утверждения очевидна: их взаимное расположение относительно других элементов не изменилось, а транспозиция этих чисел изменяет количество инверсий на единицу. Пусть теперь между перемещаемыми элементами <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> транспозиций рядом стоящих элементов, то есть чётность перестановки изменится.
}}

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

Пусть в массиве <tex>p[i]</tex> содержится перестановка, тогда в массиве <tex>rep[i]</tex>, после выполнения алгоритма, будет содержаться обратная перестановка.
'''fun''' reversePerm(p : '''int[]''', rep : '''int[]''')
'''int''' n = p.size;
'''for''' i = 0 '''to''' n
'''for''' j = 0 '''to''' n
'''if''' p[j] == i + 1
rep[i] = j + 1;

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

<tex> a = (1, 3, 2), (4, 5) \Rightarrow a^{-1} = (1, 2, 3), (4, 5) </tex>

Отсюда следует более эффективный алгоритм, где <tex> visited[] </tex> - массив посещённых элементов:
'''fun''' reversePerm (visited : '''boolean[]''', p : '''int[]''', rep : '''int[]''')
'''int''' n = p.size;
'''for''' i = 0 '''to''' n
'''if''' visited[i]
'''continue''';
''// инвертировать цикл, начинающийся в позиции <tex> i </tex> ''
'''int''' last = i;
'''int''' j = p[i];
'''while''' '''true'''
'''int''' next = p[j];
p[j] = last;
visited[j] = '''true''';
'''if''' j == i
'''break''';
last = j;
j = next;

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

{{Определение
|definition=
'''Группой''' (англ. ''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> 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>

}}

{{Утверждение
|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> \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)
* Н. И. Яцкин, Алгебра Теоремы и алгоритмы, Издательство «Ивановский государственный университет», 2006 г., стр. 161

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

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

2018-01-03T22:59:46Z

Denis:

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

{{Определение
|definition=
'''Умножением''' (англ. ''multiplication'') или '''композицией''' (англ. ''composition'') перестановок,представленных в виде целочисленных функций <tex> a_i </tex>, где <tex>i - </tex> позиция элемента, а <tex> a_i </tex> — его номер, называется перестановка, получаемая по следующему правилу:

<tex> (ab)_i = a_{b_i} </tex>

}}

{{Утверждение
|statement=
Умножение перестановок ассоциативно:

<tex> (a(bc))_i = ((ab)c)_i </tex>

|proof=

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

# <tex> (a(bc))_i = a_{(bc)_i} = a_{b_{c_i}} </tex>
# <tex> ((ab)c)_i = (ab)_{c_i} = a_{b_{c_i}} </tex>

}}

{{Определение
|definition=
'''Циклом''' (англ. cycle) перестановки называется такое упорядоченное подмножество перестановки размера <tex>k</tex>, что каждый его элемент в результате действия перестановки циклически передвигается по подмножеству.

}}
Каждую перестановку можно разбить на множество непересекающихся циклов. Например, <tex> {2, 4, 6, 1, 5, 3} = (1, 2, 4)(3, 6)(5) = (1, 2, 4)(3, 6)</tex>, циклы размера <tex>1</tex> можно опустить. Композицию перестановок можно также представить в виде произведения циклов.

===Пример===

<tex> a = {2, 5, 6, 3, 1, 4} = (1, 2, 5)(3, 6, 4) </tex>

<tex> b = {4, 1, 3, 6, 5, 2} = (1, 4, 6, 5) </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>

Просматривая произведение справа налево, рассмотрим, что произойдёт в каждом цикле. Для примера, начнём с <tex>1 </tex>. Открываем результирующий цикл, начинающийся в <tex> 1 </tex> позиции: <tex> "(1," </tex> Первый цикл, <tex> (1, 4, 6, 5) </tex> переставляет <tex> 1 </tex> с <tex> 4 </tex>, второй цикл, <tex> (3, 6, 4) </tex>, переставляет <tex> 4 </tex> с <tex> 3 </tex>, а третий цикл никак не влияет на <tex> 3 </tex>. В итоге <tex> 1 </tex> позиция переставляется с <tex> 3 </tex>: <tex> "(1, 3" </tex>. Далее рассмотрим <tex> 3 </tex>: первый цикл никак на неё не влияет, второй переставляет с <tex> 6 </tex>, третий не переставляет <tex> 6 </tex>, то есть в итоге <tex> 3 </tex> переходит в <tex> 6 </tex>: <tex> "(1, 3, 6" </tex>. Дальше вкратце: 6 <tex>\rightarrow 5 \rightarrow 1 </tex>, цикл завершился <tex> "(1, 3, 6, 5)" </tex>. Рассматриваем следующую неиспользованную позицию: <tex> 2 \rightarrow 2, "(1, 3, 6, 5)(2)", 4 \rightarrow 4 </tex>. В итоге получаем <tex> "(1, 3, 6, 5)(2)(4)" </tex>

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

{{Определение
|definition=

'''Обратной перестановкой''' (англ. ''an inverse permutation'') <tex> a^{-1} </tex> к перестановке <tex> a </tex> называется такая перестановка, что:

<tex> (a^{-1}a)_i = (aa^{-1})_i = i </tex>

}}

{{Определение
|id = def_involution
|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(n-1)</tex> инволюций, при <tex>a_n = n </tex>. Число инволюций, содержащих цикл <tex>(j,n)</tex>, где <tex> 1\leq j\leq n-1 </tex>, <tex> (n-1)\cdot I(n-2)</tex>. Имеем, что <tex> I(n) = I(n-1)+(n-1)\cdot I(n-2). </tex>

}}

{{Определение
|definition=

Перестановка, содержащая чётное количество инверсий, называется '''чётной''', в противном случае <tex> - </tex> '''нечётной'''.

}}

{{Определение
|definition=

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

}}

{{Лемма|id=lemma1
|statement=

Если в перестановке, длина которой больше <tex>1</tex>, поменять местами <tex> 2 </tex> элемента, то её четность изменится.

|proof=

Для элементов, стоящих рядом, истинность утверждения очевидна: их взаимное расположение относительно других элементов не изменилось, а транспозиция этих чисел изменяет количество инверсий на единицу. Пусть теперь между перемещаемыми элементами <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> транспозиций рядом стоящих элементов, то есть чётность перестановки изменится.
}}

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

Пусть в массиве <tex>p[i]</tex> содержится перестановка, тогда в массиве <tex>rep[i]</tex>, после выполнения алгоритма, будет содержаться обратная перестановка.
'''fun''' reversePerm(p : '''int[]''', rep : '''int[]''')
'''int''' n = p.size;
'''for''' i = 0 '''to''' n
'''for''' j = 0 '''to''' n
'''if''' p[j] == i + 1
rep[i] = j + 1;

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

<tex> a = (1, 3, 2), (4, 5) \Rightarrow a^{-1} = (1, 2, 3), (4, 5) </tex>

Отсюда следует более эффективный алгоритм, где <tex> visited[] </tex> - массив посещённых элементов:
'''fun''' reversePerm (visited : '''boolean[]''', p : '''int[]''', rep : '''int[]''')
'''int''' n = p.size;
'''for''' i = 0 '''to''' n
'''if''' visited[i]
'''continue''';
''// инвертировать цикл, начинающийся в позиции <tex> i </tex> ''
'''int''' last = i;
'''int''' j = p[i];
'''while''' '''true'''
'''int''' next = p[j];
p[j] = last;
visited[j] = '''true''';
'''if''' j == i
'''break''';
last = j;
j = next;

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

{{Определение
|definition=
'''Группой''' (англ. ''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> 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>

}}

{{Утверждение
|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> \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)
* Н. И. Яцкин, Алгебра Теоремы и алгоритмы, Издательство «Ивановский государственный университет», 2006 г., стр. 161

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

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

2018-01-03T22:07:06Z

Denis:

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

{{Определение
|definition=
'''Умножением''' (англ. ''multiplication'') или '''композицией''' (англ. ''composition'') перестановок,представленных в виде целочисленных функций <tex> a_i </tex>, где <tex>i - </tex> позиция элемента, а <tex> a_i </tex> — его номер, называется перестановка, получаемая по следующему правилу:

<tex> (ab)_i = a_{b_i} </tex>

}}

{{Утверждение
|statement=
Умножение перестановок ассоциативно:

<tex> (a(bc))_i = ((ab)c)_i </tex>

|proof=

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

# <tex> (a(bc))_i = a_{(bc)_i} = a_{b_{c_i}} </tex>
# <tex> ((ab)c)_i = (ab)_{c_i} = a_{b_{c_i}} </tex>

}}

===Пример===

<tex> a = {2, 5, 6, 3, 1, 4} = (1, 2, 5)(3, 6, 4) </tex>

<tex> b = {4, 1, 3, 6, 5, 2} = (1, 4, 6, 5) </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=

'''Обратной перестановкой''' (англ. ''an inverse permutation'') <tex> a^{-1} </tex> к перестановке <tex> a </tex> называется такая перестановка, что:

<tex> (a^{-1}a)_i = (aa^{-1})_i = i </tex>

}}

{{Определение
|id = def_involution
|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(n-1)</tex> инволюций, при <tex>a_n = n </tex>. Число инволюций, содержащих цикл <tex>(j,n)</tex>, где <tex> 1\leq j\leq n-1 </tex>, <tex> (n-1)\cdot I(n-2)</tex>. Имеем, что <tex> I(n) = I(n-1)+(n-1)\cdot I(n-2). </tex>

}}

{{Определение
|definition=

Перестановка, содержащая чётное количество инверсий, называется '''чётной''', в противном случае <tex> - </tex> '''нечётной'''.

}}

{{Определение
|definition=

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

}}

{{Лемма|id=lemma1
|statement=

Если в перестановке, длина которой больше <tex>1</tex>, поменять местами <tex> 2 </tex> элемента, то её четность изменится.

|proof=

Для элементов, стоящих рядом, истинность утверждения очевидна: их взаимное расположение относительно других элементов не изменилось, а транспозиция этих чисел изменяет количество инверсий на единицу. Пусть теперь между перемещаемыми элементами <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> транспозиций рядом стоящих элементов, то есть чётность перестановки изменится.
}}

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

Пусть в массиве <tex>p[i]</tex> содержится перестановка, тогда в массиве <tex>rep[i]</tex>, после выполнения алгоритма, будет содержаться обратная перестановка.
'''fun''' reversePerm(p : '''int[]''', rep : '''int[]''')
'''int''' n = p.size;
'''for''' i = 0 '''to''' n
'''for''' j = 0 '''to''' n
'''if''' p[j] == i + 1
rep[i] = j + 1;

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

<tex> a = (1, 3, 2), (4, 5) \Rightarrow a^{-1} = (1, 2, 3), (4, 5) </tex>

Отсюда следует более эффективный алгоритм, где <tex> visited[] </tex> - массив посещённых элементов:
'''fun''' reversePerm (visited : '''boolean[]''', p : '''int[]''', rep : '''int[]''')
'''int''' n = p.size;
'''for''' i = 0 '''to''' n
'''if''' visited[i]
'''continue''';
''// инвертировать цикл, начинающийся в позиции <tex> i </tex> ''
'''int''' last = i;
'''int''' j = p[i];
'''while''' '''true'''
'''int''' next = p[j];
p[j] = last;
visited[j] = '''true''';
'''if''' j == i
'''break''';
last = j;
j = next;

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

{{Определение
|definition=
'''Группой''' (англ. ''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> 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>

}}

{{Утверждение
|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> \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)
* Н. И. Яцкин, Алгебра Теоремы и алгоритмы, Издательство «Ивановский государственный университет», 2006 г., стр. 161

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

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

2018-01-03T20:54:00Z

Denis:

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

{{Определение
|definition=
'''Умножением''' (англ. ''multiplication'') или '''композицией''' (англ. ''composition'') перестановок,представленных в виде целочисленных функций <tex> a_i </tex>, где <tex>i - </tex> позиция элемента, а <tex> a_i </tex> — его номер, называется перестановка, получаемая по следующему правилу:

<tex> (ab)_i = a_{b_i} </tex>

}}

{{Утверждение
|statement=
Умножение перестановок ассоциативно:

<tex> (a(bc))_i = ((ab)c)_i </tex>

|proof=

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

# <tex> (a(bc))_i = a_{(bc)_i} = a_{b_{c_i}} </tex>
# <tex> ((ab)c)_i = (ab)_{c_i} = a_{b_{c_i}} </tex>

}}

===Пример===

<tex> a = {2, 5, 6, 3, 1, 4} = (1, 2, 5)(3, 6, 4) </tex>

<tex> b = {4, 1, 3, 6, 5, 2} = (1, 4, 6, 5) </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=

'''Обратной перестановкой''' (англ. ''an inverse permutation'') <tex> a^{-1} </tex> к перестановке <tex> a </tex> называется такая перестановка, что:

<tex> (a^{-1}a)_i = (aa^{-1})_i = i </tex>

}}

{{Определение
|id = def_involution
|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(n-1)</tex> инволюций, при <tex>a_n = n </tex>. Число инволюций, содержащих цикл <tex>(j,n)</tex>, где <tex> 1\leq j\leq n-1 </tex>, <tex> (n-1)\cdot I(n-2)</tex>. Имеем, что <tex> I(n) = I(n-1)+(n-1)\cdot I(n-2). </tex>

}}

{{Определение
|definition=

Перестановка, содержащая чётное количество инверсий, называется '''чётной''', в противном случае <tex> - </tex> '''нечётной'''.

}}

{{Определение
|definition=

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

}}

{{Лемма|id=lemma1
|statement=

Если в перестановке, длина которой больше <tex>1</tex>, поменять местами <tex> 2 </tex> элемента, то её четность изменится.

|proof=

Для элементов, стоящих рядом, истинность утверждения очевидна: их взаимное расположение относительно других элементов не изменилось, а транспозиция этих чисел изменяет количество инверсий на единицу. Пусть теперь между перемещаемыми элементами <tex> a </tex> и <tex> b </tex> находятся <tex> d </tex> элементов, то есть перестановка имеет вид: <tex> ..., a, s_1, s_2, ..., s_d, b, ... </tex>. Сначала поменяем последовательно <tex> a </tex> с числами <tex> s_1, s_2, ..., s_d, b </tex>, а затем число <tex>b</tex> с рядом стоящими <tex> s_d, s_d-1, ..., s_1 </tex>. В итоге мы выполним <tex> 2\cdot d + 1 </tex> транспозиций рядом стоящих элементов, то есть чётность перестановки изменится.
}}

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

Пусть в массиве <tex>p[i]</tex> содержится перестановка, тогда в массиве <tex>rep[i]</tex>, после выполнения алгоритма, будет содержаться обратная перестановка.
'''fun''' reversePerm(p : '''int[]''', rep : '''int[]''')
'''int''' n = p.size;
'''for''' i = 0 '''to''' n
'''for''' j = 0 '''to''' n
'''if''' p[j] == i + 1
rep[i] = j + 1;

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

<tex> a = (1, 3, 2), (4, 5) \Rightarrow a^{-1} = (1, 2, 3), (4, 5) </tex>

Отсюда следует более эффективный алгоритм, где <tex> visited[] </tex> - массив посещённых элементов:
'''fun''' reversePerm (visited : '''boolean[]''', p : '''int[]''', rep : '''int[]''')
'''int''' n = p.size;
'''for''' i = 0 '''to''' n
'''if''' visited[i]
'''continue''';
''// инвертировать цикл, начинающийся в позиции <tex> i </tex> ''
'''int''' last = i;
'''int''' j = p[i];
'''while''' '''true'''
'''int''' next = p[j];
p[j] = last;
visited[j] = '''true''';
'''if''' j == i
'''break''';
last = j;
j = next;

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

{{Определение
|definition=
'''Группой''' (англ. ''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> 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>

}}

{{Утверждение
|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> \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 & ... & q_n \\ a_{k_1} & a_{k_2} & ... & 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)
* Н. И. Яцкин, Алгебра Теоремы и алгоритмы, Издательство «Ивановский государственный университет», 2006 г., стр. 161

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

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

2018-01-03T19:17:42Z

Denis: цвет комментария изменён на зелёный

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

{{Определение
|definition=
'''Умножением''' (композицией) перестановок,представленных в виде целочисленных функций <tex> a_i </tex>, где <tex>i - </tex> позиция элемента, а <tex> a_i </tex> — его номер, называется перестановка, получаемая по следующему правилу:

<tex> (ab)_i = a_{b_i} </tex>

}}

{{Утверждение
|statement=
Умножение перестановок ассоциативно:

<tex> (a(bc))_i = ((ab)c)_i </tex>

|proof=

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

# <tex> (a(bc))_i = a_{(bc)_i} = a_{b_{c_i}} </tex>
# <tex> ((ab)c)_i = (ab)_{c_i} = a_{b_{c_i}} </tex>

}}

===Пример===

<tex> a = {2, 5, 6, 3, 1, 4} = (1, 2, 5)(3, 6, 4) </tex>

<tex> b = {4, 1, 3, 6, 5, 2} = (1, 4, 6, 5) </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=

'''Обратной перестановкой''' (англ. an inverse permutation) <tex> a^{-1} </tex> к перестановке <tex> a </tex> называется такая перестановка, что:

<tex> (a^{-1}a)_i = (aa^{-1})_i = i </tex>

}}

{{Определение
|id = def_involution
|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(n-1)</tex> инволюций, при <tex>a_n = n </tex>. Число инволюций, содержащих цикл <tex>(j,n)</tex>, где <tex> 1\leq j\leq n-1 </tex>, <tex> (n-1)\cdot I(n-2)</tex>. Имеем, что <tex> I(n) = I(n-1)+(n-1)\cdot I(n-2). </tex>

}}

{{Определение
|definition=

Перестановка, содержащая чётное количество инверсий, называется '''чётной''', в противном случае <tex> - </tex> '''нечётной'''.

}}

{{Определение
|definition=

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

}}

{{Лемма|id=lemma1
|statement=

Если в перестановке, длина которой больше <tex>1</tex>, поменять местами <tex> 2 </tex> элемента, то её четность изменится.

|proof=

Для элементов, стоящих рядом, истинность утверждения очевидна: их взаимное расположение относительно других элементов не изменилось, а транспозиция этих чисел изменяет количество инверсий на единицу. Пусть теперь между перемещаемыми элементами <tex> a </tex> и <tex> b </tex> находятся <tex> d </tex> элементов, то есть перестановка имеет вид: <tex> ..., a, s_1, s_2, ..., s_d, b, ... </tex>. Сначала поменяем последовательно <tex> a </tex> с числами <tex> s_1, s_2, ..., s_d, b </tex>, а затем число <tex>b</tex> с рядом стоящими <tex> s_d, s_d-1, ..., s_1 </tex>. В итоге мы выполним <tex> 2\cdot d + 1 </tex> транспозиций рядом стоящих элементов, то есть чётность перестановки изменится.
}}

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

Пусть в массиве <tex>p[i]</tex> содержится перестановка, тогда в массиве <tex>rep[i]</tex>, после выполнения алгоритма, будет содержаться обратная перестановка.
'''fun''' reversePerm(p : '''int[]''', rep : '''int[]''')
'''int''' n = p.size;
'''for''' i = 0 '''to''' n
'''for''' j = 0 '''to''' n
'''if''' p[j] == i + 1
rep[i] = j + 1;

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

<tex> a = (1, 3, 2), (4, 5) \Rightarrow a^{-1} = (1, 2, 3), (4, 5) </tex>

Отсюда следует более эффективный алгоритм, где <tex> visited[] </tex> - массив посещённых элементов:
'''fun''' reversePerm (visited : '''boolean[]''', p : '''int[]''', rep : '''int[]''')
'''int''' n = p.size;
'''for''' i = 0 '''to''' n
'''if''' visited[i]
'''continue''';
''// инвертировать цикл, начинающийся в позиции <tex> i </tex> ''
'''int''' last = i;
'''int''' j = p[i];
'''while''' '''true'''
'''int''' next = p[j];
p[j] = last;
visited[j] = '''true''';
'''if''' j == i
'''break''';
last = j;
j = next;

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

{{Определение
|definition=
'''Группой''' называется множество <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> 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>

}}

{{Утверждение
|statement=
Множество перестановок с <tex> n </tex> элементами с операцией умножения является группой (часто группу перестановок называют симметрической, и обозначают <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> \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 & ... & q_n \\ a_{k_1} & a_{k_2} & ... & 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)
* Н. И. Яцкин, Алгебра Теоремы и алгоритмы, Издательство «Ивановский государственный университет», 2006 г., стр. 161

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

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

2018-01-03T19:14:32Z

Denis: добавлена часть англ. терминов, исправлен псевдокод, ВСЕ цифры и переменные отныне добавлены в tex, добавлен пример группы подстановок

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

{{Определение
|definition=
'''Умножением''' (композицией) перестановок,представленных в виде целочисленных функций <tex> a_i </tex>, где <tex>i - </tex> позиция элемента, а <tex> a_i </tex> — его номер, называется перестановка, получаемая по следующему правилу:

<tex> (ab)_i = a_{b_i} </tex>

}}

{{Утверждение
|statement=
Умножение перестановок ассоциативно:

<tex> (a(bc))_i = ((ab)c)_i </tex>

|proof=

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

# <tex> (a(bc))_i = a_{(bc)_i} = a_{b_{c_i}} </tex>
# <tex> ((ab)c)_i = (ab)_{c_i} = a_{b_{c_i}} </tex>

}}

===Пример===

<tex> a = {2, 5, 6, 3, 1, 4} = (1, 2, 5)(3, 6, 4) </tex>

<tex> b = {4, 1, 3, 6, 5, 2} = (1, 4, 6, 5) </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=

'''Обратной перестановкой''' (англ. an inverse permutation) <tex> a^{-1} </tex> к перестановке <tex> a </tex> называется такая перестановка, что:

<tex> (a^{-1}a)_i = (aa^{-1})_i = i </tex>

}}

{{Определение
|id = def_involution
|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(n-1)</tex> инволюций, при <tex>a_n = n </tex>. Число инволюций, содержащих цикл <tex>(j,n)</tex>, где <tex> 1\leq j\leq n-1 </tex>, <tex> (n-1)\cdot I(n-2)</tex>. Имеем, что <tex> I(n) = I(n-1)+(n-1)\cdot I(n-2). </tex>

}}

{{Определение
|definition=

Перестановка, содержащая чётное количество инверсий, называется '''чётной''', в противном случае <tex> - </tex> '''нечётной'''.

}}

{{Определение
|definition=

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

}}

{{Лемма|id=lemma1
|statement=

Если в перестановке, длина которой больше <tex>1</tex>, поменять местами <tex> 2 </tex> элемента, то её четность изменится.

|proof=

Для элементов, стоящих рядом, истинность утверждения очевидна: их взаимное расположение относительно других элементов не изменилось, а транспозиция этих чисел изменяет количество инверсий на единицу. Пусть теперь между перемещаемыми элементами <tex> a </tex> и <tex> b </tex> находятся <tex> d </tex> элементов, то есть перестановка имеет вид: <tex> ..., a, s_1, s_2, ..., s_d, b, ... </tex>. Сначала поменяем последовательно <tex> a </tex> с числами <tex> s_1, s_2, ..., s_d, b </tex>, а затем число <tex>b</tex> с рядом стоящими <tex> s_d, s_d-1, ..., s_1 </tex>. В итоге мы выполним <tex> 2\cdot d + 1 </tex> транспозиций рядом стоящих элементов, то есть чётность перестановки изменится.
}}

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

Пусть в массиве <tex>p[i]</tex> содержится перестановка, тогда в массиве <tex>rep[i]</tex>, после выполнения алгоритма, будет содержаться обратная перестановка.
'''fun''' reversePerm(p : '''int[]''', rep : '''int[]''')
'''int''' n = p.size;
'''for''' i = 0 '''to''' n
'''for''' j = 0 '''to''' n
'''if''' p[j] == i + 1
rep[i] = j + 1;

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

<tex> a = (1, 3, 2), (4, 5) \Rightarrow a^{-1} = (1, 2, 3), (4, 5) </tex>

Отсюда следует более эффективный алгоритм, где <tex> visited[] </tex> - массив посещённых элементов:
'''fun''' reversePerm (visited : '''boolean[]''', p : '''int[]''', rep : '''int[]''')
'''int''' n = p.size;
'''for''' i = 0 '''to''' n
'''if''' visited[i]
'''continue''';
// инвертировать цикл, начинающийся в позиции <tex> i </tex>
'''int''' last = i;
'''int''' j = p[i];
'''while''' '''true'''
'''int''' next = p[j];
p[j] = last;
visited[j] = '''true''';
'''if''' j == i
'''break''';
last = j;
j = next;

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

{{Определение
|definition=
'''Группой''' называется множество <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> 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>

}}

{{Утверждение
|statement=
Множество перестановок с <tex> n </tex> элементами с операцией умножения является группой (часто группу перестановок называют симметрической, и обозначают <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> \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 & ... & q_n \\ a_{k_1} & a_{k_2} & ... & 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)
* Н. И. Яцкин, Алгебра Теоремы и алгоритмы, Издательство «Ивановский государственный университет», 2006 г., стр. 161

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

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

2017-12-31T20:02:18Z

Denis: Как-то так оформил тикет

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

{{Определение
|definition=
'''Умножением''' (композицией) перестановок,представленных в виде целочисленных функций <tex> a_i </tex>, где <tex>i - </tex> позиция элемента, а <tex> a_i </tex> — его номер, называется перестановка, получаемая по следующему правилу:

<tex> (ab)_i = a_{b_i} </tex>

}}

{{Утверждение
|statement=
Умножение перестановок ассоциативно:

<tex> (a(bc))_i = ((ab)c)_i </tex>

|proof=

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

# <tex> (a(bc))_i = a_{(bc)_i} = a_{b_{c_i}} </tex>
# <tex> ((ab)c)_i = (ab)_{c_i} = a_{b_{c_i}} </tex>

}}

===Пример===

<tex> a = {2, 5, 6, 3, 1, 4} = (1, 2, 5)(3, 6, 4) </tex>

<tex> b = {4, 1, 3, 6, 5, 2} = (1, 4, 6, 5) </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=

'''Обратной''' перестановкой <tex> a^{-1} </tex> к перестановке <tex> a </tex> называется такая перестановка, что:

<tex> (a^{-1}a)_i = (aa^{-1})_i = i </tex>

}}

{{Определение
|id = def_involution
|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(n-1)</tex> инволюций, при <tex>a_n = n </tex>. Число инволюций, содержащих цикл <tex>(j,n)</tex>, где <tex> 1\leq j\leq n-1 </tex>, <tex> (n-1)\cdot I(n-2)</tex>. Имеем, что <tex> I(n) = I(n-1)+(n-1)\cdot I(n-2). </tex>

}}

{{Определение
|definition=

Перестановка, содержащая чётное количество инверсий, называется '''чётной''', в противном случае <tex> - </tex> '''нечётной'''.

}}

{{Определение
|definition=

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

}}

{{Лемма|id=lemma1
|statement=

Если в перестановке, длина которой больше <tex>1</tex>, поменять местами <tex> 2 </tex> элемента, то её четность изменится.

|proof=

Для элементов, стоящих рядом, истинность утверждения очевидна: их взаимное расположение относительно других элементов не изменилось, а транспозиция этих чисел изменяет количество инверсий на единицу. Пусть теперь между перемещаемыми элементами <tex> a </tex> и <tex> b </tex> находятся <tex> d </tex> элементов, то есть перестановка имеет вид: <tex> ..., a, s_1, s_2, ..., s_d, b, ... </tex>. Сначала поменяем последовательно <tex> a </tex> с числами <tex> s_1, s_2, ..., s_d, b </tex>, а затем число <tex>b</tex> с рядом стоящими <tex> s_d, s_d-1, ..., s_1 </tex>. В итоге мы выполним <tex> 2\cdot d + 1 </tex> транспозиций рядом стоящих элементов, то есть чётность перестановки изменится.
}}

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

Пусть в массиве 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;

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

<tex> a = (1, 3, 2), (4, 5) \Rightarrow a^{-1} = (1, 2, 3), (4, 5) </tex>

Отсюда следует более эффективный алгоритм (приведена in-place версия):

boolean[] visited = new boolean[n];
for (int i = 0; i < n; ++i)
if (visited[i]) continue;
// Reverse the cycle starting at i
int last = i;
int j = p[i];
while (true)
int next = p[j];
p[j] = last;
visited[j] = true;
if (j == i) break;
last = j;
j = next;

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

{{Определение
|definition=
'''Группой''' называется множество <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> 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>

}}

{{Утверждение
|statement=
Множество перестановок с <tex> n </tex> элементами с операцией умножения является группой (часто группу перестановок называют симметрической, и обозначают <tex> S_n </tex>).
|proof=
Свойства 1 и 3 доказаны выше, а в качестве нейтрального элемента выступает тождественная перестановка (<tex> \pi_i = i </tex>).
}}

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

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

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

{{Определение
|definition=
'''Группа чётных перестановок''' <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> натуральных чисел на себя.

}}

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

<tex> A = \begin{pmatrix} q_1 & q_2 & ... & q_n \\ a_{k_1} & a_{k_2} & ... & a_{k_n} \end{pmatrix} </tex>

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

==Источники и литература==
* https://en.wikipedia.org/wiki/Involution_(mathematics)
* Н. И. Яцкин, Алгебра Теоремы и алгоритмы, Издательство «Ивановский государственный университет», 2006 г., стр. 161

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]