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

(перенаправлено с «Цикловой индекс»)

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

История

править

Впервые эта теорема была получена и опубликована Редфилдом[англ.] в 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 с.