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


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

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

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

Содержание

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

Пусть заданы два конечных множества 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 симметрической группы Sn. Введем отношение эквивалентности на 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 симметрической группы Sn определяется как многочлен от 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)},

где jk(a) — число циклов длины k в перестановке a.

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

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

C(t) = Z_A(c(t),c(t^2),\ldots,c(t^n)),

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

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

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

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

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

Решение. Пусть множество X = \{ 1, 2, \ldots, n \} соответствует номерам бусинок в браслете, а Y = {0,1} — множество возможных цветов. Весовую функцию положим равной w(y) = y для всех y\in Y. Во множестве Y имеется один элемент веса 0 и один — веса 1, то есть c0 = 1 и c1 = 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) равно Ck, коэффициенту при tk в 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.
  • «Комбинаторная прикладная математика». Под ред. Э.Беккенбаха. М.: Мир, 1968.
  • Л. А. Калужнин, В. И. Сущанский «Преобразования и перестановки». M.: Наука, 1985.
  • Ф.Харари «Теория графов». М.: Мир, 1973.
  • Ф.Харари, Э.Палмер «Перечисление графов». М.: Мир, 1977.
  • Д. И. Яковенко «Задача об ожерельях». Вестник Омского университета, 1998, Вып. 2, стр. 21-24.

Wikimedia Foundation. 2010.

Смотреть что такое "Цикловой индекс" в других словарях:

  • Индекс — (лат. index список, реестр, указатель) число, буквы или другая комбинация символов, указывающая место элемента в совокупности или характеризующая состояние некоторой системы, например показатель активности, производительности, развития,… …   Википедия

  • Индекс — (Index) Определение индекса, виды индексов, расчет индексов Информация об определении индекса, виды индексов, расчет индексов Содержание Содержание Определение Морса Индекс подгруппы Индекс (поисковой машины) Индекс (базы ) Ветро холодовой индекс …   Энциклопедия инвестора

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

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

  • ПОЙА ТЕОРЕМА — пусть RD множество отображений конечного множества D, |D|=n, в множество R и пусть G группа подстановок множества D, порождающая разбиение RD на классы эквивалентности, при к ром принадлежат одному и тому же классу тогда и только тогда, когда… …   Математическая энциклопедия

  • Бензин — (Petrol) Бензин это самое распространенное топливо для большинства видов транспорта Подробная информация о составе, получении, хранении и применении бензина Содержание >>>>>>>>>>>>>> …   Энциклопедия инвестора

  • Мирелль — Латинское название Mirelle АТХ: ›› G03AA10 Гестоден и эстрогены Фармакологическая группа: Эстрогены, гестагены; их гомологи и антагонисты Нозологическая классификация (МКБ 10) ›› Z30.0 Общие советы и консультации по контрацепции Состав и форма… …   Словарь медицинских препаратов

  • ГАЗ-21 — ГАЗ 21 …   Википедия

  • Волга 21 — «Волга» ГАЗ 21 «Волга» ГАЗ 21 на викискладе …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.