Умножение перестановок, обратная перестановка, группа перестановок
Умножение перестановок
Определение: |
Умножением (композицией) перестановок называется перестановка, получающаяся по следующему правилу: |
Утверждение: |
Умножение перестановок ассоциативно:
|
Доказывается простым раскрытием скобок. |
Пример
Обратная перестановка
Определение: |
Обратной перестановкой | к перестановке называется такая перестановка, что:
При представлении перестановки в виде циклов обратную перестановку можно легко получить, инвертировав все ребра в циклах.
Определение: |
Перестановка, равная своей обратной, называется инволюцией: |
Утверждение: |
Число инволюций можно посчитать, используя рекуррентную формулу:
|
Доказательство: Рассмотрим n-ый элемент перестановки. Возможны два случая, где он может находиться:
|
Группа перестановок
Определение: |
Пусть Тогда группой называется алгебраическая структура, удовлетворяющая следующим свойствам:
| - множество, , и на этом множестве задана бинарная операция , такая, что .
Утверждение: |
Множество перестановок с элементами с операцией умножения является группой (часто группу перестановок называют симметрической, и обозначают ). |
Свойства 1 и 3 доказаны выше, а в качестве нейтрального элемента можно брать тождественную перестановку ( Перестановка, имеющая нейтральный элемент, называется моноидом. ). |
Мощность множества симметрических групп:
Теорема Кэли утверждает, что любая конечная группа изоморфна подгруппе соответствующей группе перестановок.