Теорема (теория) Редфилда — Пойа — классический результат перечислительной комбинаторики.

Впервые эта теорема была получена и опубликована Редфилдом в 1927 году, но работа была сочтена весьма специальной и осталась незамеченной. Пойа независимо доказал то же самое в 1937 году, но оказался куда более успешным популяризатором — так, например, в первой же публикации он показал применимость этого результата к перечислению химических соединений.

Вводные определения

Пусть заданы два конечных множества и , а также весовая функция . Положим . Без потери общности можно считать, что .

Рассмотрим множество функций . При этом вес функции определяется как

.

Пусть на множестве действует некоторая подгруппа симметрической группы . Введем отношение эквивалентности на

для некоторого .

Класс эквивалентности обозначим через и будем называть орбитой . Так как веса эквивалентных функций совпадают, то можно определить вес орбиты как .

Пусть

 — число элементов веса ;

 — число орбит веса ;

и  — соответствующие производящие функции.

Цикловой индекс

Цикловой индекс подгруппы симметрической группы определяется как многочлен от переменных

где  — число циклов длины в перестановке .

Теорема Редфилда—Пойа

Теорема Редфилда—Пойа утверждает, что

где  — цикловой индекс группы .

Доказательство теоремы Редфилда—Пойа опирается на лемму Бернсайда.

Примеры приложений

Задача о количестве ожерелий

Задача. Найти количество ожерелий, составленных из n бусинок двух цветов. Ожерелья, совпадающие при повороте, считаются одинаковыми.

Решение. Пусть множество соответствует номерам бусинок в ожерелье, а — множество возможных цветов. Весовую функцию положим равной для всех . Во множестве имеется один элемент веса 0 и один — веса 1, то есть и . Откуда .

Пусть — множество всех функций из в . Любая функция задает некоторое ожерелье и, наоборот, каждое ожерелье задаётся некоторой функцией из . При этом вес функции равен количеству бусинок цвета 1 в соответствующем ожерелье.

На множестве действует группа поворотов , порожденная циклической перестановкой , которая определяет отношение эквивалентности на . Тогда ожерелья совпадающие при повороте будут в точности соответствовать эквивалентным функциям, и задача сводится к подсчёту числа орбит.

Цикловой индекс группы равен

,

где — функция Эйлера, — наибольший общий делитель чисел и .

По теореме Редфилда-Пойа

Число орбит веса (то есть различных ожерельев с бусинками цвета 1) равно , коэффициенту при в :

.

Общее число различных орбит (или ожерелий) равно

Литература

• Перечислительные задачи комбинаторного анализа / Сборник переводов под редакцией Г. П. Гаврилова. — М.: Мир, 1979.
• Комбинаторная прикладная математика / Под ред. Э.Беккенбаха. — М.: Мир, 1968.
• Л. А. Калужнин, В. И. Сущанский Преобразования и перестановки. — M.: Наука, 1985.
• Ф.Харари Теория графов. — М.: Мир, 1973.
• Ф.Харари, Э.Палмер Перечисление графов. — М.: Мир, 1977.
• Д. И. Яковенко Задача об ожерельях // Вестник Омского университета. — 1998. — В. 2. — С. 21-24.