Теорема (теория) Редфилда — Пойи — классический результат перечислительной комбинаторики.
История
правитьВпервые эта теорема была получена и опубликована Редфилдом[англ.] в 1927 году, но работа была сочтена весьма специальной и осталась незамеченной. Пойа независимо доказал то же самое в 1937 году, но оказался куда более успешным популяризатором — так, например, в первой же публикации он показал применимость этого результата к перечислению химических соединений[1].
Вводные определения
правитьПусть заданы два конечных множества и , а также весовая функция . Положим . Без потери общности можно считать, что .
Рассмотрим множество функций . При этом вес функции определяется как
- .
Пусть на множестве действует некоторая подгруппа симметрической группы . Введем отношение эквивалентности на
- для некоторого .
Класс эквивалентности обозначим через и будем называть орбитой . Так как веса эквивалентных функций совпадают, то можно определить вес орбиты как .
Пусть
- — число элементов веса ;
- — число орбит веса ;
- и — соответствующие производящие функции.
Цикловой индекс
правитьЦикловой индекс подгруппы симметрической группы определяется как многочлен от переменных
где — число циклов длины в перестановке .
Теорема Редфилда — Пойи
правитьТеорема Редфилда — Пойи утверждает, что
где — цикловой индекс группы [2][3].
Доказательство теоремы Редфилда — Пойи опирается на лемму Бёрнсайда[4][5].
Известны многочисленные обобщения теоремы Редфилда — Пойи[6].
Примеры приложений
правитьЗадача о количестве ожерелий
правитьЗадача. Найти количество ожерелий, составленных из бусинок двух цветов. Ожерелья, совпадающие при повороте, считаются одинаковыми (перевороты не допускаются).
Решение. Пусть множество соответствует номерам бусинок в ожерелье, а — множество возможных цветов. Весовую функцию положим равной для всех . Во множестве имеется один элемент веса 0 и один — веса 1, то есть и . Откуда .
Пусть — множество всех функций из в . Любая функция задаёт некоторое ожерелье и, наоборот, каждое ожерелье задаётся некоторой функцией из . При этом вес функции равен количеству бусинок цвета 1 в соответствующем ожерелье.
На множестве действует группа поворотов , порожденная циклической перестановкой , которая определяет отношение эквивалентности на . Тогда ожерелья совпадающие при повороте будут в точности соответствовать эквивалентным функциям, и задача сводится к подсчёту числа орбит.
Цикловой индекс группы равен
где — функция Эйлера, — наибольший общий делитель чисел и .
По теореме Редфилда — Пойи,
Число орбит веса (то есть различных ожерелий с бусинками цвета 1) равно , коэффициенту при в :
Общее число различных орбит (или ожерелий) равно
Примечания
править- ↑ Pólya G. Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen // Acta Mathematica. — 1937. — Vol. 68. — P. 145—254. — doi:10.1007/BF02546665.
- ↑ Нефедов, 1992, с. 156.
- ↑ Рыбников, 1972, с. 71.
- ↑ Нефедов, 1992, с. 157—159.
- ↑ Рыбников, 1972, с. 72—74.
- ↑ Рыбников, 1972, с. 74.
Литература
править- Перечислительные задачи комбинаторного анализа / Сборник переводов под редакцией Г. П. Гаврилова. — М.: Мир, 1979.
- Комбинаторная прикладная математика / Под ред. Э.Беккенбаха. — М.: Мир, 1968.
- Калужнин Л. А., Сущанский В. И. Преобразования и перестановки. — M.: Наука, 1985.
- Харари Ф. Теория графов. — М.: Мир, 1973.
- Харари Ф., Палмер Э. Перечисление графов. — М.: Мир, 1977.
- Яковенко Д. И. Задача об ожерельях // Вестник Омского университета. — 1998. — Вып. 2. — С. 21—24. Архивировано 8 мая 2005 года.
- Рыбников К. А. Введение в комбинаторный анализ. — М.: МГУ, 1972. — 253 с.
- Нефедов В. Н., Осипова В. А. Курс дискретной математики. — М.: МАИ, 1992. — 262 с.