imported>G2ii2g: /* История */ викификация

2021-03-07T22:16:16Z

История: викификация

Новая страница

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

== История ==

Впервые эта теорема была получена и опубликована {{нп3|Редфилд, Джон Говард|Редфилдом||J. Howard Redfield}} в [[1927 год]]у, но работа была сочтена весьма специальной и осталась незамеченной. [[Пойа]] независимо доказал то же самое в [[1937 год]]у, но оказался куда более успешным популяризатором — так, например, в первой же публикации он показал применимость этого результата к перечислению [[химическое соединение|химических соединений]]<ref name="Polya">{{статья|автор=Pólya G.|заглавие=Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen|издание=[[Acta Mathematica]]|volume=68|год=1937|issue=1|pages=145—254|url=http://www.springerlink.com/content/9021012252111875/|doi=10.1007/BF02546665}}</ref>.

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

Пусть заданы два конечных множества <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|Нефедов|с=156|1992}}{{sfn|Рыбников|с=71|1972}}.

Доказательство теоремы Редфилда — Пойи опирается на [[Лемма Бёрнсайда|лемму Бёрнсайда]]{{sfn|Нефедов|с=157—159|1992}}{{sfn|Рыбников|с=72—74|1972}}.

Известны многочисленные обобщения теоремы Редфилда — Пойи{{sfn|Рыбников|с=74|1972}}.

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

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

'''Задача.''' Найти количество ожерелий, составленных из <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>

== Примечания ==
{{примечания}}

== Литература ==
* {{книга |заглавие=Перечислительные задачи комбинаторного анализа |ответственный=Сборник переводов под редакцией Г. П. Гаврилова |место=М. |издательство=Мир |год=1979}}
* {{книга |заглавие=Комбинаторная прикладная математика |ответственный=Под ред. Э.Беккенбаха |место=М. |издательство=Мир |год=1968}}
* {{книга |автор=Калужнин Л. А., Сущанский В. И.|заглавие=Преобразования и перестановки |место=M. |издательство=Наука |год=1985}}
* {{книга |автор=Харари Ф.|заглавие=Теория графов |место=М. |издательство=Мир |год=1973}}
* {{книга |автор=Харари Ф., Палмер Э.|заглавие=Перечисление графов |место=М. |издательство=Мир |год=1977}}
* {{статья |автор=Яковенко Д. И. |заглавие=Задача об ожерельях |издание=Вестник Омского университета |год=1998 |выпуск=2 |страницы=21—24 |ссылка=http://www.omsu.omskreg.ru/vestnik/articles/y1998-i2/a021/article.html |archiveurl=https://web.archive.org/web/20050508125709/http://www.omsu.omskreg.ru/vestnik/articles/y1998-i2/a021/article.html |archivedate=2005-05-08 }}
* {{книга |автор=[[Рыбников, Константин Алексеевич|Рыбников К. А.]]|заглавие=Введение в комбинаторный анализ |место=М. |
издательство=МГУ | страниц=253 |год=1972|ref=Рыбников}}
* {{книга |автор=Нефедов В. Н., Осипова В. А.|заглавие=Курс дискретной математики |место=М. |
издательство=МАИ | страниц=262 |год=1992|ref=Нефедов}}

[[Категория:Комбинаторика]]
[[Категория:Теоремы дискретной математики|Редфилда — Пойа]]
[[Категория:Математическая химия]]
[[Категория:Теоремы теории графов]]

Теорема Редфилда — Пойи - История изменений

imported>G2ii2g: /* История */ викификация