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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

Вводные определения[править | править вики-текст]

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

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

.

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

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

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

Пусть

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

Цикловой индекс[править | править вики-текст]

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

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

Теорема Редфилда—Пойа[править | править вики-текст]

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

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

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

Примеры приложений[править | править вики-текст]

Задача о количестве ожерелий[править | править вики-текст]

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

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

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

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

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

,

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

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

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

.

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

Примечания[править | править вики-текст]

  1. G. Pólya Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen // Acta Mathematica. — 1937. — Vol. 68. — P. 145–254. — DOI:10.1007/BF02546665.

Литература[править | править вики-текст]

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