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

Перейти к навигацииПерейти к поиску

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

История

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

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

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

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

.

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

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

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

Пусть

 — число элементов веса ;
 — число орбит веса ;
и  — соответствующие производящие функции.

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

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

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

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

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

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

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

Известны многочисленные обобщения теоремы Редфилда — Пойи[6].

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

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

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

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

Пусть  — множество всех функций из в . Любая функция задаёт некоторое ожерелье и, наоборот, каждое ожерелье задаётся некоторой функцией из . При этом вес функции равен количеству бусинок цвета 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.
  2. Нефедов, 1992, с. 156.
  3. Рыбников, 1972, с. 71.
  4. Нефедов, 1992, с. 157—159.
  5. Рыбников, 1972, с. 72—74.
  6. Рыбников, 1972, с. 74.

Литература

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