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

Материал из Википедии — свободной энциклопедии

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

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

Содержание

1 Вводные определения
- 1.1 Цикловой индекс
2 Теорема Редфилда—Пойа
3 Примеры приложений
- 3.1 Задача о количестве браслетов
4 Литература

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

Пусть заданы два конечных множества $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} \phi(n/d) t_{n/d}^d = \frac{1}{n} \sum_{d|n} \phi(d) t_d^{n/d}$ ,

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

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

$C(t) = Z_A(1+t,1+t^2,\ldots,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) {n/d\choose k/d}$ .

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

$\sum_k C_k = C(1) = \frac{1}{n} \sum_{d|n} \phi(d) 2^{n/d}$

[править] Литература

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

Категории: Комбинаторика | Теоремы | Химия | Теория графов

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

Материал из Википедии — свободной энциклопедии

Содержание

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

[править] Цикловой индекс

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

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

[править] Задача о количестве браслетов

[править] Литература

Views

Навигация

Участие

Поиск

На других языках