p>
Для того, щоб привести класичну формулу перерахування Пойа, ми візьмемо B=E - одиничної групі на безлічі Y. Розглянемо тепер ступеневу групу, що діяла на множині. Нехай - функція, область значень якої є безліччю невід'ємних цілих чисел і для якої при всіх k. У термінах теорії перерахування для кожного називають числом «фігур» ваги k.
Про елементі y з Y, для якого, кажуть, що він має вагу k, а функцію w називають ваговій функцією. Далі, ряд
відносно змінної x, який перераховує елементи множини Y відповідно до їх вагами, називають «перераховують поруч для фігур».
Вага функції f з YX визначається формулою
і тоді неважко показати, що функції, які належать одній і тій же орбіті статечної групи, мають однакові ваги. Вагою w (F) орбіти F групи назвемо вага будь-якої функції f з орбіти F. Так як для всякого k=0, 1, 2, ..., то існує тільки кінцеве число орбіт кожної ваги. Позначимо через число орбіт ваги k. Ряд відносно змінної x назвемо «перераховують поруч для функцій» або «перераховують поруч для конфігурацій».
Тепер ми можемо сформулювати основну теорему, що виражає ряд C (x) у термінах циклового індексу Z (A) і ряду c (x). У наведеній нижче формулі Z (A, c (x)) є скороченням для Z (A, c (x), c (), c (), ...).
Теорема (теорема перерахування Пойа, 1927)
Ряд C (x), що перераховує функції, виходить за допомогою підстановки в циклової індекс Z (A) на місце кожної змінної ряду перераховує фігури. Символічно:
Доказ. Нехай e - тотожна підстановка на Y. Для всякої підстановки a з A і будь-якого k=0, 1, 2, ... позначимо через ц (a, k) число функцій ваги k, нерухомих щодо підстановки (a; e). Обмежуючи для кожного k дію статечної групи на безліч функцій ваги k і застосовуючи обмежену форму леми Бернсайда (1.13), маємо
Отже,
і, змінюючи порядок підсумовування, отримуємо
Ряд перераховує всі функції, нерухомі щодо підстановки (a; e), і ми постараємося знайти іншу форму для цього ряду.
Припустимо, що функція f з непожвіжна щодо підстановки (a; e). Тоді для всіх x з X і в силу формули (1.14), маємо. Таким чином, для всіх x повинно виконуватися рівність, тобто функція f має бути постійною на непересічних циклах підстановки a. Зворотно, всі функції, постійні на циклах підстановки a, нерухомі щодо підстановки (a; e).
Нехай - цикл довжини r в підстановці a. Якщо функція f відображає елементи циклу в один з елементів множини Y, що мають вагу k, то цикл вносить у вагу функції f значення r · k. Тоді легко бачити, що для кожного k коефіцієнт при в ряду
дорівнює числу способів, якими можна визначити функцію f на елементах циклу так, щоб вона була нерухома щодо підстановки (a; e) і щоб внесок у вагу w (f) становив r · k. Звідси випливає, що ряд перераховує відповідно до їх вагами різні способи визначення функцій, постійних на всіх циклах довжини r підстановки a.
Розглядаючи всі цикли підстановки a, ми можемо висловити ряд для функцій, постійних на циклах, у вигляді твору
Тепер твердження теореми Пойа (18) випливає з (1.21), (1.23) і визначення циклового індексу Z (A).
2. Практичне застосування Теореми Пойа та перерахування графів
.1 Рішення задач про перерахування графів за доп...
