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

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

01 марта 2011

Оглавление:
1. Теорема Редфилда Пойа
2. Теорема Редфилда—Пойа

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

$C = Z_A,c,\ldots,c),$

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

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

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

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

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

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

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

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