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

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

История

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

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

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

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

[math]\displaystyle{ w(f) = \sum_{x\in X} w\left(f(x)\right) }[/math].

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

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

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

Пусть

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

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

[math]\displaystyle{ c(t) = \sum_k c_k\cdot t^k }[/math] и [math]\displaystyle{ C(t) = \sum_k C_k\cdot t^k }[/math] — соответствующие производящие функции.

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

Цикловой индекс подгруппы [math]\displaystyle{ A }[/math] симметрической группы [math]\displaystyle{ S_n }[/math] определяется как многочлен от [math]\displaystyle{ n }[/math] переменных [math]\displaystyle{ t_1,t_2,\ldots,t_n }[/math]

[math]\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)}, }[/math]

где [math]\displaystyle{ j_k(a) }[/math] — число циклов длины [math]\displaystyle{ k }[/math] в перестановке [math]\displaystyle{ a }[/math].

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

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

[math]\displaystyle{ C(t) = Z_A\big(c(t), c(t^2), \ldots, c(t^n)\big), }[/math]

где [math]\displaystyle{ Z_A }[/math] — цикловой индекс группы [math]\displaystyle{ A }[/math].

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

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

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

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

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

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

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

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

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

[math]\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}, }[/math]

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

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

[math]\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}. }[/math]

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

[math]\displaystyle{ C_k = \frac{1}{n} \sum_{d|(n,k)} \varphi(d) \binom{n/d}{k/d}. }[/math]

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

[math]\displaystyle{ \sum_k C_k = C(1) = \frac{1}{n} \sum_{d|n} \varphi(d) 2^{n/d}. }[/math]

Литература

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