) (4) перетворює вершини 1 і 4 в вершини 3 і 4, і ці образи 3 і 4, також є суміжними. Таким чином, підстановка (13) (2) (4) зберігає суміжність вершин 1 і 4. Так як сукупність підстановок в цьому списку замкнута щодо операції множення, то вона утворює групу.
Тепер можемо переходити до визначення такого поняття, як циклової індекс групи підстановок.
Нехай A - група підстановок з безліччю об'єктів і - деяка підстановка з цієї групи. Для кожного через позначимо число циклів довжини в розкладанні підстановки у твір непересічних циклів.
Тоді циклової індекс групи, що позначається або, являє собою многочлен від змінних, який визначається формулою:
Розглянемо для прикладу симметрическую групу. Зауважимо, що тотожна підстановка (1) (2) (3) має три одиничних циклу дають доданок. Три підстановки (1) (23), (2) (13) і (3) (12) мають кожна по одиничному циклу і по одному циклу довжини 2, так що виходить один доданок. Нарешті, підстановки (123) і (132) вносять. Таким чином, маємо
Для обчислення циклового індексу симетричної групи введемо поняття розбиття числа і розглянемо кілька тверджень.
Назвемо розбиттям натурального числа n його подання у вигляді суми деяких натуральних чисел. Зауважимо, що кожна підстановка a на n об'єктах може бути пов'язана з певним розбиттям числа n, що має для кожного точно частин, рівних числу k. Будемо здавати розбиття числа n допомогою вектора, де - число частин розбиття, рівних k. Отже,
Приклад
4=1 + 1 + 1 + 1 (4, 0, 0, 0)
=1 + 1 + 2 (2, 1, 0, 0)
=2 + 2 (0, 2, 0, 0)
=1 + 3 (1, 0, 1, 0)
=4 (0, 0, 0, 1)
Нехай h (j) - число підстановок в групі, розкладання яких на непересічні цикли відповідає разбиению (j), в тому сенсі, що для кожного k виконується. Тоді має місце наступна лема.
Лемма
Таким чином, після приведення подібних членів у виразі (1.1), циклової індекс прийме наступний вигляд.
Теорема
Цикловий індекс симетричної групи дається формулою
де сума береться по всіх розбиття (j) числа n, а h (j) задається виразом
(1.2).
Приклад
3=1 + 1 + 1 (3, 0, 0) h=3!/3! =1
=1 + 2 (1, 1, 0) h=3!/1.1! · 2.1! =3
=3 (0, 0, 1) h=3!/3.1!
Іноді зручно расматривать виробляє функцію циклових індексів і користуватися наступним властивістю.
Теорема
де за визначенням.
Часто буває зручним виразити через, де. Рекурентна формула, наступна з (1.4), може бути представлена ??наступним чином.
Теорема Цикловий індекс симетричної групи задовольняє рекурентному співвідношенню
Приклад
1.2 Еквівалентність, породжувана групою підстановок
Ставлення еквівалентності
Ставлення еквівалентності на безлічі - це бінарне відношення, для якого виконані наступні умови:
· Рефлексивность: для будь-якого в,
· Симетричність: якщо, то,
· Транзитивність: якщо й, то.
Запис виду «» читається як «a еквівалентно b».
Нехай A - група підстановок з безліччю об'єктів. Елементи x і y з X називаються A-еквівалентними, якщо існує підстановка a з A, така, що. Неважко пока...
