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

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

ИсторияПравить

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

Вводные определенияПравить

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

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

$w(f)=\underset{x\in <!--\; \in \; -->X}{\sum <!--\; \sum \; -->}w\left(f(x)\right)$$w(f)=\sum _{x\in X}w\left(f(x)\right)$ .

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

$f\sim <!--\; \sim \; -->g⟺<!--\; ⟺\; -->f=g\circ <!--\; \circ \; -->a$$f\sim g\quad \Longleftrightarrow \quad f=g\circ a$  для некоторого $a\in <!--\; \in \; -->A$$a\in A$ .

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

Пусть

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

$C_k=\left|\{[f]\mid <!--\; \mid \; -->w([f])=k\}\right|$$C_{k}=\left|\{[f]\mid w([f])=k\}\right|$  — число орбит веса $k$$k$ ;

$c(t)=\underset{k}{\sum <!--\; \sum \; -->}{c}_k\cdot <!--\; \cdot \; -->t^k$$c(t)=\sum _{k}c_{k}\cdot t^{k}$  и $C(t)=\underset{k}{\sum <!--\; \sum \; -->}{C}_k\cdot <!--\; \cdot \; -->t^k$$C(t)=\sum _{k}C_{k}\cdot t^{k}$  — соответствующие производящие функции.

Цикловой индексПравить

Цикловой индекс подгруппы $A$$A$  симметрической группы $S_n$$S_{n}$  определяется как многочлен от $n$$n$  переменных $t_1,t_2,\dots <!--\; \dots \; -->,t_n$$t_{1},t_{2},\ldots ,t_{n}$ 

$Z_A(t_1,t_2,\dots <!--\; \dots \; -->,t_n)=\frac{1}{|A|}\underset{a\in <!--\; \in \; -->A}{\sum <!--\; \sum \; -->}{t}_1^{j_1(a)}\cdot <!--\; \cdot \; -->t_2^{j_2(a)}\cdot <!--\; \cdot \; -->\dots <!--\; \dots \; -->\cdot <!--\; \cdot \; -->t_n^{j_n(a)},$$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)$$j_{k}(a)$  — число циклов длины $k$$k$  в перестановке $a$$a$ .

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

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

$C(t)=Z_A(c(t),c(t^2),\dots <!--\; \dots \; -->,c(t^n)),$$C(t)=Z_{A}{\big (}c(t),c(t^{2}),\ldots ,c(t^{n}){\big )},$ 

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

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

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

Примеры приложенийПравить

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

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

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

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

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

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

$Z_A(t_1,\dots <!--\; \dots \; -->,t_n)=\frac{1}{n}\underset{k=1}{\overset{n}{\sum <!--\; \sum \; -->}}{t}_{n/(k,n)}^{(k,n)}=\frac{1}{n}\underset{d\mid <!--\; \mid \; -->n}{\sum <!--\; \sum \; -->}\mathrm{\phi <!--\; \phi \; -->}(n/d)t_{n/d}^d=\frac{1}{n}\underset{d|n}{\sum <!--\; \sum \; -->}\mathrm{\phi <!--\; \phi \; -->}(d)t_d^{n/d},$$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},$ 

где $\mathrm{\phi <!--\; \phi \; -->}(d)$$\varphi (d)$  — функция Эйлера, $(k,n)$$(k,n)$  — наибольший общий делитель чисел $k$$k$  и $n$$n$ .

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

$C(t)=Z_A(1+t,1+t^2,\dots <!--\; \dots \; -->,1+t^n)=\frac{1}{n}\underset{d|n}{\sum <!--\; \sum \; -->}\mathrm{\phi <!--\; \phi \; -->}(d)(1+t^d{)}^{n/d}.$$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$  (то есть различных ожерелий с $k$$k$  бусинками цвета 1) равно $C_k$$C_{k}$ , коэффициенту при $t^k$$t^{k}$  в $C(t)$$C(t)$ :

$C_k=\frac{1}{n}\underset{d|(n,k)}{\sum <!--\; \sum \; -->}\mathrm{\phi <!--\; \phi \; -->}(d)(\genfrac{}{}{0ex}{}{n/d}{k/d}).$$C_{k}={\frac {1}{n}}\sum _{d|(n,k)}\varphi (d){\binom {n/d}{k/d}}.$ 

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

$\underset{k}{\sum <!--\; \sum \; -->}{C}_k=C(1)=\frac{1}{n}\underset{d|n}{\sum <!--\; \sum \; -->}\mathrm{\phi <!--\; \phi \; -->}(d)2^{n/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. Архивировано 8 мая 2005 года.
• Рыбников К. А. Введение в комбинаторный анализ. — М.: МГУ, 1972. — 253 с.
• Нефедов В. Н., Осипова В. А. Курс дискретной математики. — М.: МАИ, 1992. — 262 с.