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

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

История

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

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

Пусть заданы два конечных множества ${\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}$[2][3].

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

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

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

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

Задача. Найти количество ожерелий, составленных из ${\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}.}$

Примечания

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 с.