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

История

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

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

Пусть заданы два конечных множества ${\displaystyle X}$ и ${\displaystyle Y}$ , а также весовая функция ${\displaystyle w:Y\rightarrow \mathbb {N} }$ . Положим ${\displaystyle n=|X|}$ . Без потери общности можно считать, что ${\displaystyle X=\{1,2,\ldots ,n\}}$ .

Рассмотрим множество функций ${\displaystyle F=\{f\mid f:X\rightarrow Y\}}$ . При этом вес функции ${\displaystyle f}$ определяется как

${\displaystyle w(f)=\sum _{x\in X}w\left(f(x)\right)}$ .

Пусть на множестве ${\displaystyle X}$ действует некоторая подгруппа ${\displaystyle A}$ симметрической группы ${\displaystyle S_{n}}$ . Введем отношение эквивалентности на ${\displaystyle F}$

${\displaystyle f\sim g\quad \Longleftrightarrow \quad f=g\circ a}$ для некоторого ${\displaystyle a\in A}$ .

Класс эквивалентности ${\displaystyle f}$ обозначим через ${\displaystyle [f]}$ и будем называть орбитой ${\displaystyle f}$ . Так как веса эквивалентных функций совпадают, то можно определить вес орбиты как ${\displaystyle w([f])=w(f)}$ .

Пусть

${\displaystyle c_{k}=\left|\{y\in Y\mid w(y)=k\}\right|}$ — число элементов ${\displaystyle Y}$ веса ${\displaystyle k}$ ;

${\displaystyle C_{k}=\left|\{[f]\mid w([f])=k\}\right|}$ — число орбит веса ${\displaystyle k}$ ;

${\displaystyle c(t)=\sum _{k}c_{k}\cdot t^{k}}$ и ${\displaystyle C(t)=\sum _{k}C_{k}\cdot t^{k}}$ — соответствующие производящие функции .

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

Цикловой индекс подгруппы ${\displaystyle A}$ симметрической группы ${\displaystyle S_{n}}$ определяется как многочлен от ${\displaystyle n}$ переменных ${\displaystyle t_{1},t_{2},\ldots ,t_{n}}$

${\displaystyle Z_{A}(t_{1},t_{2},\ldots ,t_{n})={\frac {1}{|A|}}\sum _{a\in A}t_{1}^{j_{1}(a)}\cdot t_{2}^{j_{2}(a)}\cdot \ldots \cdot t_{n}^{j_{n}(a)},}$

где ${\displaystyle j_{k}(a)}$ — число циклов длины ${\displaystyle k}$ в перестановке ${\displaystyle a}$ .

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

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

${\displaystyle C(t)=Z_{A}{\big (}c(t),c(t^{2}),\ldots ,c(t^{n}){\big )},}$

где ${\displaystyle Z_{A}}$ — цикловой индекс группы ${\displaystyle A}$ .

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

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

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

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

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

Решение. Пусть множество ${\displaystyle X=\{1,2,\ldots ,n\}}$ соответствует номерам бусинок в ожерелье, а ${\displaystyle Y=\{0,1\}}$ — множество возможных цветов. Весовую функцию положим равной ${\displaystyle w(y)=y}$ для всех ${\displaystyle y\in Y}$ . Во множестве ${\displaystyle Y}$ имеется один элемент веса 0 и один — веса 1, то есть ${\displaystyle c_{0}=1}$ и ${\displaystyle c_{1}=1}$ . Откуда ${\displaystyle c(t)=1+t}$ .

Пусть ${\displaystyle F=\{f\mid f:X\to Y\}}$ — множество всех функций из ${\displaystyle X}$ в ${\displaystyle Y}$ . Любая функция ${\displaystyle f\in F}$ задаёт некоторое ожерелье и, наоборот, каждое ожерелье задаётся некоторой функцией из ${\displaystyle F}$ . При этом вес функции равен количеству бусинок цвета 1 в соответствующем ожерелье.

На множестве ${\displaystyle X}$ действует группа поворотов ${\displaystyle A}$ , порожденная циклической перестановкой ${\displaystyle (1,2,\ldots ,n)}$ , которая определяет отношение эквивалентности на ${\displaystyle F}$ . Тогда ожерелья совпадающие при повороте будут в точности соответствовать эквивалентным функциям, и задача сводится к подсчёту числа орбит.

Цикловой индекс группы ${\displaystyle A}$ равен

${\displaystyle Z_{A}(t_{1},\ldots ,t_{n})={\frac {1}{n}}\sum _{k=1}^{n}t_{n/(k,n)}^{(k,n)}={\frac {1}{n}}\sum _{d\mid n}\varphi (n/d)t_{n/d}^{d}={\frac {1}{n}}\sum _{d|n}\varphi (d)t_{d}^{n/d},}$

где ${\displaystyle \varphi (d)}$ — функция Эйлера , ${\displaystyle (k,n)}$ — наибольший общий делитель чисел ${\displaystyle k}$ и ${\displaystyle n}$ .

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

${\displaystyle C(t)=Z_{A}(1+t,1+t^{2},\ldots ,1+t^{n})={\frac {1}{n}}\sum _{d|n}\varphi (d)(1+t^{d})^{n/d}.}$

Число орбит веса ${\displaystyle k}$ (то есть различных ожерелий с ${\displaystyle k}$ бусинками цвета 1 ) равно ${\displaystyle C_{k}}$ , коэффициенту при ${\displaystyle t^{k}}$ в ${\displaystyle C(t)}$ :

${\displaystyle C_{k}={\frac {1}{n}}\sum _{d|(n,k)}\varphi (d){\binom {n/d}{k/d}}.}$

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

${\displaystyle \sum _{k}C_{k}=C(1)={\frac {1}{n}}\sum _{d|n}\varphi (d)2^{n/d}.}$

Примечания

Литература

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