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

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

История

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

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

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

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

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

.

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

f\sim g\quad \Longleftrightarrow \quad f=g\circ a

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

a\in A

.

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

Пусть

c_{k}=\left|\{y\in Y\mid w(y)=k\}\right|

— число элементов

Y

веса

k

;

C_{k}=\left|\{[f]\mid w([f])=k\}\right|

— число орбит веса

k

;

c(t)=\sum _{k}c_{k}\cdot t^{k}

и

C(t)=\sum _{k}C_{k}\cdot t^{k}

— соответствующие производящие функции.

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

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

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)},

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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},

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

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

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

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

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

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

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

Примечания

Pólya G. Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen // Acta Mathematica. — 1937. — Vol. 68. — P. 145—254. — doi:10.1007/BF02546665.
Нефедов, 1992, с. 156.
Рыбников, 1972, с. 71.
Нефедов, 1992, с. 157—159.
Рыбников, 1972, с. 72—74.
Рыбников, 1972, с. 74.

Литература

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[Polya-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.

[_5dcb074a6a4e6868-2] Нефедов, 1992, с. 156.

[_4c7da97a31342b66-3] Рыбников, 1972, с. 71.

[_e51786979dca4694-4] Нефедов, 1992, с. 157—159.

[_3718d86355dcdc08-5] Рыбников, 1972, с. 72—74.

[_4c7da97a31342b63-6] Рыбников, 1972, с. 74.