Теорема Редфилда

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

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

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

Пусть заданы два конечных множества $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(c(t),c(t^2),\ldots,c(t^n)),$

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

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

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

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

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

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

$\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.