, 2) і (3, 4) нерухомі; (1, 3)? (2, 4)? (1, 3); (1, 4)? 2, 3)? (1, 4). Відповідний одночлен -. Так як в S4 три 2,2-циклу, то вони дають в циклових індекс вклад.
Приклад. Нехай n=4. Ми знаємо, що. Є 5 разбиений числа 4: 4, 3 + 1, 2 + 2, 2 + 1 + 1, 1 + 1 + 1 + 1.
· Перше розбиття відповідає нагоди зв'язного графа - таких графів 6.
· Друге розбиття відповідає нагоди двох компонент зв'язності - з трьома вершинами і з однією вершиною. Таких графів 2.
· Третє розбиття відповідає нагоди двох компонент зв'язності - з двома вершинами кожна. Такий граф один.
· Четверте розбиття відповідає нагоди трьох компонент зв'язності - одна з двома вершинами і дві з однією вершиною. Такий графів один.
· П'яте розбиття відповідає нагоди чотирьох компонент зв'язності - з однією вершиною кожна. Такий граф один.
Отже,=11.
Мовою виробляють рядів цю конструкцію можна описати так. Кількість графів з n вершинами дорівнює коефіцієнту при tn у творі рядів
(1 + t + + + ...)? (1 + + + ...)? (1 + + + ...)?. . .
Тут коефіцієнт дорівнює числу графів, що складаються з j зв'язкових компонент, причому кожна компонента має i вершин. Тоесть - це кількість способів вибрати j зв'язкових графів з, причому у вибірці можуть бути й однакові графи.
Таким чином,
і i-й співмножник в творі є
Отже
Перейдемо до логарифмам
Розкладемо кожен логарифм в ряд і наведемо подібні. Легко бачити, що в розкладанні в статечної ряд доданок з'являється лише в тому випадку, коли i - дільник n. Тоді відповідний коефіцієнт дорівнює. Отже,
Де
Тут сума береться по всіх делителям числа n. Таким чином,
Правило переходу від досить просте. Дійсно, продифференцируем це рівність. Маємо (2.10)
Тепер порівнюємо коефіцієнти при:
Так як, то ми отримали рекуррентную формулу для обчислення чисел
Приклад. Знайти кількість намист, складених з n бусинок двох кольорів. Намиста, що збігаються при повороті, вважаються однаковими.
Нехай безліч відповідає номерам бусинок в намисто, а - безліч можливих кольорів. Вагову функцію покладемо рівною для всіх. У безлічі є один елемент ваги 0 і один - ваги 1, тобто і. Звідки.
Нехай - множина всіх функцій з в. Будь функція задає деякий намисто і, навпаки, кожне намисто задається деякою функцією з. При цьому вага функції дорівнює кількості бусинок кольору 1 у відповідному намисто.
На безлічі діє група поворотів, породжена циклічної перестановкою, яка визначає ставлення еквівалентності на. Тоді намиста збігаються при повороті з точністю відповідати еквівалентним функціям, і завдання зводиться до підрахунку числа орбіт.
Цикловий індекс групи дорівнює
,
де - функція Ейлера, - найбільший спільний дільник чисел і.
По теоремі Редфилда-Пойа
Число орбіт ваги (тобто різних намиста з нами...
