Теорема (теория) Редфилда — Пойи — классический результат перечислительной комбинаторики.
История
Впервые эта теорема была получена и опубликована в 1927 году, но работа была сочтена весьма специальной и осталась незамеченной. Пойа независимо доказал то же самое в 1937 году, но оказался куда более успешным популяризатором — так, например, в первой же публикации он показал применимость этого результата к перечислению химических соединений.
Вводные определения
Пусть заданы два конечных множества и , а также весовая функция . Положим . Без потери общности можно считать, что .
Рассмотрим множество функций . При этом вес функции определяется как .
Пусть на множестве действует некоторая подгруппа симметрической группы . Введем отношение эквивалентности на для некоторого . Класс эквивалентности обозначим через и будем называть орбитой . Так как веса эквивалентных функций совпадают, то можно определить вес орбиты как .
Пусть — число элементов веса ; — число орбит веса ; и — соответствующие производящие функции.
Цикловой индекс
Цикловой индекс подгруппы симметрической группы определяется как многочлен от переменных
где — число циклов длины в перестановке .
Теорема Редфилда — Пойи
Теорема Редфилда — Пойи утверждает, что
где — цикловой индекс группы .
Доказательство теоремы Редфилда — Пойи опирается на лемму Бёрнсайда.
Известны многочисленные обобщения теоремы Редфилда — Пойи.
Примеры приложений
Задача о количестве ожерелий
Задача. Найти количество ожерелий, составленных из бусинок двух цветов. Ожерелья, совпадающие при повороте, считаются одинаковыми (перевороты не допускаются).
Решение. Пусть множество соответствует номерам бусинок в ожерелье, а — множество возможных цветов. Весовую функцию положим равной для всех . Во множестве имеется один элемент веса 0 и один — веса 1, то есть и . Откуда .
Пусть — множество всех функций из в . Любая функция задаёт некоторое ожерелье и, наоборот, каждое ожерелье задаётся некоторой функцией из . При этом вес функции равен количеству бусинок цвета 1 в соответствующем ожерелье.
На множестве действует группа поворотов , порожденная циклической перестановкой , которая определяет отношение эквивалентности на . Тогда ожерелья совпадающие при повороте будут в точности соответствовать эквивалентным функциям, и задача сводится к подсчёту числа орбит.
Цикловой индекс группы равен
где — функция Эйлера, — наибольший общий делитель чисел и .
По теореме Редфилда — Пойи,
Число орбит веса (то есть различных ожерелий с бусинками цвета 1) равно , коэффициенту при в :
Общее число различных орбит (или ожерелий) равно
Примечания
Литература
Категория:Комбинаторика Редфилда — Пойа Категория:Математическая химия Категория:Теоремы теории графов