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

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

История

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

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

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

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

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

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

$f\sim g⟺f=g\circ a$ для некоторого $a\in A$.

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

Пусть

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

$C_k=|\{[f]\mid w([f])=k\}|$ — число орбит веса $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,\dots ,t_n$

$Z_A(t_1,t_2,\dots ,t_n)=\frac{1}{|A|}\sum _{a\in A}{t}_1^{j_1(a)}\cdot t_2^{j_2(a)}\cdot \dots \cdot t_n^{j_n(a)},$

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

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

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

$C(t)=Z_A(c(t),c(t^2),\dots ,c(t^n)),$

где $Z_A$ — цикловой индекс группы $A$Шаблон:SfnШаблон:Sfn.

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

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

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

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

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

Решение. Пусть множество $X=\{1,2,\dots ,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,\dots ,n)$, которая определяет отношение эквивалентности на $F$. Тогда ожерелья совпадающие при повороте будут в точности соответствовать эквивалентным функциям, и задача сводится к подсчёту числа орбит.

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

$Z_A(t_1,\dots ,t_n)=\frac{1}{n}\sum _{k=1}^n{t}_{n/(k,n)}^{(k,n)}=\frac{1}{n}\sum _{d\mid n}\phi (n/d)t_{n/d}^d=\frac{1}{n}\sum _{d|n}\phi (d)t_d^{n/d},$

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

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

$C(t)=Z_A(1+t,1+t^2,\dots ,1+t^n)=\frac{1}{n}\sum _{d|n}\phi (d)(1+t^d{)}^{n/d}.$

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

$C_k=\frac{1}{n}\sum _{d|(n,k)}\phi (d)(\genfrac{}{}{0ex}{}{n/d}{k/d}).$

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

$\sum _k{C}_k=C(1)=\frac{1}{n}\sum _{d|n}\phi (d)2^{n/d}.$

Литература

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Книга