Русская Википедия:Теорема Редфилда — Пойи
Теорема (теория) Редфилда — Пойи — классический результат перечислительной комбинаторики.
История
Впервые эта теорема была получена и опубликована Шаблон:Нп3 в 1927 году, но работа была сочтена весьма специальной и осталась незамеченной. Пойа независимо доказал то же самое в 1937 году, но оказался куда более успешным популяризатором — так, например, в первой же публикации он показал применимость этого результата к перечислению химических соединений[1].
Вводные определения
Пусть заданы два конечных множества <math>X</math> и <math>Y</math>, а также весовая функция <math>w:Y\rightarrow \mathbb{N}</math>. Положим <math>n=|X|</math>. Без потери общности можно считать, что <math>X = \{1,2,\ldots,n\}</math>.
Рассмотрим множество функций <math>F = \{ f\mid f:X\rightarrow Y \}</math>. При этом вес функции <math>f</math> определяется как
- <math>w(f) = \sum_{x\in X} w\left(f(x)\right)</math>.
Пусть на множестве <math>X</math> действует некоторая подгруппа <math>A</math> симметрической группы <math>S_n</math>. Введем отношение эквивалентности на <math>F</math>
- <math>f \sim g\quad\Longleftrightarrow\quad f = g\circ a</math> для некоторого <math>a\in A</math>.
Класс эквивалентности <math>f</math> обозначим через <math>[f]</math> и будем называть орбитой <math>f</math>. Так как веса эквивалентных функций совпадают, то можно определить вес орбиты как <math>w([f]) = w(f)</math>.
Пусть
- <math>c_k = \left|\{ y\in Y \mid w(y)=k \}\right|</math> — число элементов <math>Y</math> веса <math>k</math>;
- <math>C_k = \left|\{ [f] \mid w([f])=k \}\right|</math> — число орбит веса <math>k</math>;
- <math>c(t) = \sum_k c_k\cdot t^k</math> и <math>C(t) = \sum_k C_k\cdot t^k</math> — соответствующие производящие функции.
Цикловой индекс
Цикловой индекс подгруппы <math>A</math> симметрической группы <math>S_n</math> определяется как многочлен от <math>n</math> переменных <math>t_1,t_2,\ldots,t_n</math>
- <math>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>j_k(a)</math> — число циклов длины <math>k</math> в перестановке <math>a</math>.
Теорема Редфилда — Пойи
Теорема Редфилда — Пойи утверждает, что
- <math>C(t) = Z_A\big(c(t), c(t^2), \ldots, c(t^n)\big),</math>
где <math>Z_A</math> — цикловой индекс группы <math>A</math>Шаблон:SfnШаблон:Sfn.
Доказательство теоремы Редфилда — Пойи опирается на лемму БёрнсайдаШаблон:SfnШаблон:Sfn.
Известны многочисленные обобщения теоремы Редфилда — ПойиШаблон:Sfn.
Примеры приложений
Задача о количестве ожерелий
Задача. Найти количество ожерелий, составленных из <math>n</math> бусинок двух цветов. Ожерелья, совпадающие при повороте, считаются одинаковыми (перевороты не допускаются).
Решение. Пусть множество <math>X = \{ 1, 2, \ldots, n \}</math> соответствует номерам бусинок в ожерелье, а <math>Y = \{ 0, 1 \}</math> — множество возможных цветов. Весовую функцию положим равной <math>w(y) = y</math> для всех <math>y \in Y</math>. Во множестве <math>Y</math> имеется один элемент веса 0 и один — веса 1, то есть <math>c_0 = 1</math> и <math>c_1 = 1</math>. Откуда <math>c(t) = 1 + t</math>.
Пусть <math>F = \{ f\mid f: X \to Y \}</math> — множество всех функций из <math>X</math> в <math>Y</math>. Любая функция <math>f \in F</math> задаёт некоторое ожерелье и, наоборот, каждое ожерелье задаётся некоторой функцией из <math>F</math>. При этом вес функции равен количеству бусинок цвета 1 в соответствующем ожерелье.
На множестве <math>X</math> действует группа поворотов <math>A</math>, порожденная циклической перестановкой <math>(1, 2, \ldots, n)</math>, которая определяет отношение эквивалентности на <math>F</math>. Тогда ожерелья совпадающие при повороте будут в точности соответствовать эквивалентным функциям, и задача сводится к подсчёту числа орбит.
Цикловой индекс группы <math>A</math> равен
- <math>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>\varphi(d)</math> — функция Эйлера, <math>(k, n)</math> — наибольший общий делитель чисел <math>k</math> и <math>n</math>.
По теореме Редфилда — Пойи,
- <math>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>k</math> (то есть различных ожерелий с <math>k</math> бусинками цвета 1) равно <math>C_k</math>, коэффициенту при <math>t^k</math> в <math>C(t)</math>:
- <math>C_k = \frac{1}{n} \sum_{d|(n,k)} \varphi(d) \binom{n/d}{k/d}.</math>
Общее число различных орбит (или ожерелий) равно
- <math>\sum_k C_k = C(1) = \frac{1}{n} \sum_{d|n} \varphi(d) 2^{n/d}.</math>
Примечания
Литература
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Книга
