Умножение перестановок, обратная перестановка, группа перестановок — различия между версиями
Denis (обсуждение | вклад) (цвет комментария изменён на зелёный) |
Denis (обсуждение | вклад) |
||
Строка 3: | Строка 3: | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
− | '''Умножением''' (композицией) перестановок,представленных в виде целочисленных функций <tex> a_i </tex>, где <tex>i - </tex> позиция элемента, а <tex> a_i </tex> — его номер, называется перестановка, получаемая по следующему правилу: | + | '''Умножением''' (англ. ''multiplication'') или '''композицией''' (англ. ''composition'') перестановок,представленных в виде целочисленных функций <tex> a_i </tex>, где <tex>i - </tex> позиция элемента, а <tex> a_i </tex> — его номер, называется перестановка, получаемая по следующему правилу: |
<tex> (ab)_i = a_{b_i} </tex> | <tex> (ab)_i = a_{b_i} </tex> | ||
Строка 41: | Строка 41: | ||
|definition= | |definition= | ||
− | '''Обратной перестановкой''' (англ. an inverse permutation) <tex> a^{-1} </tex> к перестановке <tex> a </tex> называется такая перестановка, что: | + | '''Обратной перестановкой''' (англ. ''an inverse permutation'') <tex> a^{-1} </tex> к перестановке <tex> a </tex> называется такая перестановка, что: |
<tex> (a^{-1}a)_i = (aa^{-1})_i = i </tex> | <tex> (a^{-1}a)_i = (aa^{-1})_i = i </tex> | ||
Строка 50: | Строка 50: | ||
|id = def_involution | |id = def_involution | ||
|definition= | |definition= | ||
− | Перестановка, равная своей обратной, называется '''инволюцией''' (англ. involution): | + | Перестановка, равная своей обратной, называется '''инволюцией''' (англ. ''involution''): |
<tex> a_i = a^{-1}_i \Rightarrow (aa ^{-1})_i = (aa)_i = a_{a_i} = i </tex>, то есть её представление в виде циклов не содержит цикла, размер которого больше двух. | <tex> a_i = a^{-1}_i \Rightarrow (aa ^{-1})_i = (aa)_i = a_{a_i} = i </tex>, то есть её представление в виде циклов не содержит цикла, размер которого больше двух. | ||
Строка 74: | Строка 74: | ||
|definition= | |definition= | ||
− | Перестановка, меняющая местами только два элемента, называется '''транспозицией''' (англ. transposition). | + | Перестановка, меняющая местами только два элемента, называется '''транспозицией''' (англ. ''transposition''). |
}} | }} | ||
Строка 124: | Строка 124: | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
− | '''Группой''' называется множество <tex> M </tex> с заданной на нём бинарной операцией <tex> \circ: МM\times M \longrightarrow M</tex>, удовлетворяющей следующим свойствам: | + | '''Группой''' (англ. ''group'') называется множество <tex> M </tex> с заданной на нём бинарной операцией <tex> \circ: МM\times M \longrightarrow M</tex>, удовлетворяющей следующим свойствам: |
# <tex> (g_1 \circ g_2) \circ g_3 = g_1 \circ (g_2 \circ g_3) </tex> — ассоциативность соответствующей бинарной операции. | # <tex> (g_1 \circ g_2) \circ g_3 = g_1 \circ (g_2 \circ g_3) </tex> — ассоциативность соответствующей бинарной операции. | ||
Строка 134: | Строка 134: | ||
{{Утверждение | {{Утверждение | ||
|statement= | |statement= | ||
− | Множество перестановок с <tex> n </tex> элементами с операцией умножения является группой (часто группу перестановок называют симметрической, и обозначают <tex> S_n </tex>). | + | Множество перестановок с <tex> n </tex> элементами с операцией умножения является группой (часто группу перестановок называют симметрической (англ. ''symmetric group''), и обозначают <tex> S_n </tex>). |
|proof= | |proof= | ||
Свойства <tex>1</tex> и <tex>3</tex> доказаны выше, а в качестве нейтрального элемента выступает тождественная перестановка (<tex> \pi_i = i </tex>). | Свойства <tex>1</tex> и <tex>3</tex> доказаны выше, а в качестве нейтрального элемента выступает тождественная перестановка (<tex> \pi_i = i </tex>). | ||
Строка 147: | Строка 147: | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
− | '''Группа чётных перестановок''' (англ. alternating group)<tex> A_n </tex> является подгруппой симметричной группы перестановок, образованной всеми чётными перестановками. Композиция не выводит из группы, так как если представить каждую перестановку группы в виде чётного числа транспозиций и перемножить их, чётность не изменится. | + | '''Группа чётных перестановок''' (англ. ''alternating group'')<tex> A_n </tex> является подгруппой симметричной группы перестановок, образованной всеми чётными перестановками. Композиция не выводит из группы, так как если представить каждую перестановку группы в виде чётного числа транспозиций и перемножить их, чётность не изменится. |
}} | }} | ||
Строка 161: | Строка 161: | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
− | '''Подстановкой''' (англ. substitution) называется всякое взаимно однозначное отображение <tex> A </tex> множества первых <tex>n</tex> натуральных чисел на себя. | + | '''Подстановкой''' (англ. ''substitution'') называется всякое взаимно однозначное отображение <tex> A </tex> множества первых <tex>n</tex> натуральных чисел на себя. |
}} | }} | ||
Строка 173: | Строка 173: | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
− | '''Группой подстановок''' (англ. group of substitutions) называется некоторая совокупность подстановок, замкнутая относительно композиции отображений, определяющей бинарную операцию для подстановок на одном и том же множестве. | + | '''Группой подстановок''' (англ. ''group of substitutions'') называется некоторая совокупность подстановок, замкнутая относительно композиции отображений, определяющей бинарную операцию для подстановок на одном и том же множестве. |
}} | }} |
Версия 23:54, 3 января 2018
Содержание
Умножение перестановок
Определение: |
Умножением (англ. multiplication) или композицией (англ. composition) перестановок,представленных в виде целочисленных функций | , где позиция элемента, а — его номер, называется перестановка, получаемая по следующему правилу:
Утверждение: |
Умножение перестановок ассоциативно:
|
Доказывается простым раскрытием скобок. |
Пример
или
Обратная перестановка
Определение: |
Обратной перестановкой (англ. an inverse permutation) | к перестановке называется такая перестановка, что:
Определение: |
Перестановка, равная своей обратной, называется инволюцией (англ. involution): | , то есть её представление в виде циклов не содержит цикла, размер которого больше двух.
Утверждение: |
Количество инволюционных перестановок длины может быть получено по формуле: , где |
Существует | инволюций, при . Число инволюций, содержащих цикл , где , . Имеем, что
Определение: |
Перестановка, содержащая чётное количество инверсий, называется чётной, в противном случае | нечётной.
Определение: |
Перестановка, меняющая местами только два элемента, называется транспозицией (англ. transposition). |
Лемма: |
Если в перестановке, длина которой больше , поменять местами элемента, то её четность изменится. |
Доказательство: |
Для элементов, стоящих рядом, истинность утверждения очевидна: их взаимное расположение относительно других элементов не изменилось, а транспозиция этих чисел изменяет количество инверсий на единицу. Пусть теперь между перемещаемыми элементами | и находятся элементов, то есть перестановка имеет вид: . Сначала поменяем последовательно с числами , а затем число с рядом стоящими . В итоге мы выполним транспозиций рядом стоящих элементов, то есть чётность перестановки изменится.
Получение обратной перестановки
Пусть в массиве
содержится перестановка, тогда в массиве , после выполнения алгоритма, будет содержаться обратная перестановка.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;
При представлении перестановки в виде циклов обратную перестановку можно легко получить, инвертировав все ребра в циклах.
Отсюда следует более эффективный алгоритм, где
- массив посещённых элементов: fun reversePerm (visited : boolean[], p : int[], rep : int[])
int n = p.size;
for i = 0 to n
if visited[i]
continue;
// инвертировать цикл, начинающийся в позиции
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;
Группа перестановок
Определение: |
Группой (англ. group) называется множество
| с заданной на нём бинарной операцией , удовлетворяющей следующим свойствам:
Утверждение: |
Множество перестановок с элементами с операцией умножения является группой (часто группу перестановок называют симметрической (англ. symmetric group), и обозначают ). |
Свойства | и доказаны выше, а в качестве нейтрального элемента выступает тождественная перестановка ( ).
Мощность симметрической группы:
Теорема Кэли утверждает, что любая конечная группа изоморфна подгруппе некоторой группе перестановок.
Группа чётных перестановок
Определение: |
Группа чётных перестановок (англ. alternating group) | является подгруппой симметричной группы перестановок, образованной всеми чётными перестановками. Композиция не выводит из группы, так как если представить каждую перестановку группы в виде чётного числа транспозиций и перемножить их, чётность не изменится.
Утверждение: |
Количество чётных перестановок длины равно количеству нечётных и равно |
Пусть число число чётных перестановок | , а нечётных . Сделаем транспозицию для всех чётных перестановок. Получим нечётных различных перестановок, то есть . Проделаем то же самое с нечётными перестановками. Получим, что , то есть и .
Группа подстановок
Определение: |
Подстановкой (англ. substitution) называется всякое взаимно однозначное отображение | множества первых натуральных чисел на себя.
Всякая подстановка может быть записана при помощи двух перестановок, подписанных одна под другой:
Где через
обозначается то число, в которое при подстановке переходит число .
Определение: |
Группой подстановок (англ. group of substitutions) называется некоторая совокупность подстановок, замкнутая относительно композиции отображений, определяющей бинарную операцию для подстановок на одном и том же множестве. |
Источники и литература
- https://en.wikipedia.org/wiki/Involution_(mathematics)
- Н. И. Яцкин, Алгебра Теоремы и алгоритмы, Издательство «Ивановский государственный университет», 2006 г., стр. 161