- Теорема Редфилда — Пойа
-
Теорема Редфилда — Пойа
Теорема (теория) Редфилда — Пойа — классический результат перечислительной комбинаторики.
Впервые эта теорема была получена и опубликована Редфилдом в 1927 году, но работа была сочтена весьма специальной и осталась незамеченной. Пойа независимо доказал то же самое в 1937 году, но оказался куда более успешным популяризатором — так, например, в первой же публикации он показал применимость этого результата к перечислению химических соединений.
Содержание
Вводные определения
Пусть заданы два конечных множества X и Y, а также весовая функция . Положим n = | X | . Без потери общности можно считать, что .
Рассмотрим множество функций . При этом вес функции f определяется как
- .
Пусть на множестве X действует некоторая подгруппа A симметрической группы Sn. Введем отношение эквивалентности на F
- для некоторого .
Класс эквивалентности f обозначим через [f] и будем называть орбитой f. Так как веса эквивалентных функций совпадают, то можно определить вес орбиты как w([f]) = w(f).
Пусть
- — число элементов Y веса k;
- — число орбит веса k;
- и — соответствующие производящие функции.
Цикловой индекс
Цикловой индекс подгруппы A симметрической группы Sn определяется как многочлен от n переменных
где jk(a) — число циклов длины k в перестановке a.
Теорема Редфилда—Пойа
Теорема Редфилда—Пойа утверждает, что
где ZA — цикловой индекс группы A.
Доказательство теоремы Редфилда—Пойа опирается на лемму Бернсайда.
Примеры приложений
Задача о количестве ожерелий
Задача. Найти количество ожерелий, составленных из n бусинок двух цветов. Ожерелья, совпадающие при повороте, считаются одинаковыми.
Решение. Пусть множество соответствует номерам бусинок в ожерелье, а Y = {0,1} — множество возможных цветов. Весовую функцию положим равной w(y) = y для всех . Во множестве Y имеется один элемент веса 0 и один — веса 1, то есть c0 = 1 и c1 = 1. Откуда c(t) = 1 + t.
Пусть — множество всех функций из X в Y. Любая функция задает некоторое ожерелье и, наоборот, каждое ожерелье задаётся некоторой функцией из F. При этом вес функции равен количеству бусинок цвета 1 в соответствующем ожерелье.
На множестве X действует группа поворотов A, порожденная циклической перестановкой , которая определяет отношение эквивалентности на F. Тогда ожерелья совпадающие при повороте будут в точности соответствовать эквивалентным функциям, и задача сводится к подсчёту числа орбит.
Цикловой индекс группы A равен
- ,
где φ(d) — функция Эйлера, (k,n) — наибольший общий делитель чисел k и n.
По теореме Редфилда-Пойа
Число орбит веса k (то есть различных ожерельев с k бусинками цвета 1) равно Ck, коэффициенту при tk в C(t):
- .
Общее число различных орбит (или ожерелий) равно
Литература
- Перечислительные задачи комбинаторного анализа / Сборник переводов под редакцией Г. П. Гаврилова. — М.: Мир, 1979.
- Комбинаторная прикладная математика / Под ред. Э.Беккенбаха. — М.: Мир, 1968.
- Л. А. Калужнин, В. И. Сущанский Преобразования и перестановки. — M.: Наука, 1985.
- Ф.Харари Теория графов. — М.: Мир, 1973.
- Ф.Харари, Э.Палмер Перечисление графов. — М.: Мир, 1977.
- Д. И. Яковенко Задача об ожерельях // Вестник Омского университета. — 1998. — В. 2. — С. 21-24.
Wikimedia Foundation. 2010.
Теорема Редфилда — Теорема (теория) Редфилда Пойа классический результат перечислительной комбинаторики. Впервые эта теорема была получена и опубликована Редфилдом в 1927 году, но работа была сочтена весьма специальной и осталась незамеченной. Пойа независимо… … Википедия
Теорема Редфилда-Пойа — … Википедия
Теорема Редфилда—Пойа — … Википедия
Цикловой индекс — Теорема (теория) Редфилда Пойа классический результат перечислительной комбинаторики. Впервые эта теорема была получена и опубликована Редфилдом в 1927 году, но работа была сочтена весьма специальной и осталась незамеченной. Пойа независимо… … Википедия
Индекс — (лат. index список, реестр, указатель) число, буквы или другая комбинация символов, указывающая место элемента в совокупности или характеризующая состояние некоторой системы, например показатель активности, производительности, развития,… … Википедия