Перегляд вихідного коду сторінки Теорема перерахування Поя

'''Теорема перерахування Поя''', також відома як '''теорема Редфілда-Поя''', теорема в [[Комбінаторика|комбінаториці]], що випливає з та узагальнює [[Лема Бернсайда|лему Бернсайда]] про кількість [[Дія групи#Орбіти_елементів|орбіт]] [[Дія групи|дії групи]] на множині. Теорему вперше було опубліковано {{Нп|Джон Говард Редфілд|Джоном Говардом Редфілдом||John 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>

Теорему перерахування Поя може бути включено до {{Нп|Символьні методи (комбінаторика)|символьних методів комбінаторики||Symbolic method (combinatorics)}} та до {{Нп|Комбінаторні види|комбінаторних видів||Combinatorial species}}.

== Спрощена, невиважена версія ==

Нехай <math>X</math> скінченна множина, та <math>G</math> є групою [[Перестановка|перестановок]] з <math>X</math> (або скінченною [[Групи симетрії|групою симетрій]], яка діє на <math>X</math>). Множина X може бути кінцевою множиною кульок, а <math>G</math> може бути обраною групою перестановок кульок. Наприклад, якщо <math>X</math> є [[Намисто (комбінаторика)|намисто]] з <math>n</math> кульок, то важлива поворотна симетрія, так що <math>G</math> є циклічною групою <math>C_n</math>, в той час як, якщо <math>X</math> є намистом, а повороти та відображення мають відношення, так що <math>G</math>&nbsp;— діедральна група <math>D_n</math> порядку <math>2n</math>.

Нехай, що <math>Y</math>&nbsp;— кінцевий набір &nbsp;— кольору кульок&nbsp;— так що <math>Y^X</math>— безліч кольорових аранжувань намист (більш формально: <math>Y^X</math>&nbsp;— множина функцій <math>{\displaystyle X\to Y}</math>)

Тоді група <math>G</math> діє на <math>Y^X</math>. У теоремі перерахування Поя підраховується число орбіт під <math>G</math> кольорових аранжувань кульок за такою формулою:

<math>|Y^X/G| = \frac{1}{|G|}\sum_{g \in G} m^{c(g)},</math>

де <math>m =  | Y |</math> це кількість кольорів і <math> c(g)</math> є число циклів групового елемента <math>g </math>, коли розглядаються як перестановки <math>X</math>.

== Повна, зважена версія ==
У більш загальній та важливішій версії теореми кольори також зважуються одним або кількома способами, і  кількість кольорів може бути нескінченна за умови, що набір кольорів має [[Генератриса|твірну функцію]] з кінцевими коефіцієнтами. В одномайновій справі, припустимо, що

<math>f (t) = f_0 + f_1 t + f_2 t ^ 2 + ...</math>

є [[Генератриса|твірною функцією]] набору кольорів, тож існує <math>f_w</math> кольорів ваги <math>w</math> для кожного цілого <math>w\geq0</math>. У багатоваріантному випадку вага кожного кольору є вектором цілих чисел і є батьківська функція <math>f(t1,t2,...)</math>, яка табулює кількість кольорів із кожним уведеним важелем. Теорія перерахунку використовує іншу багатомірну твірну функцію, яка називається індексом циклу :

<math>Z_G(t_1,t_2,\ldots,t_n) = \frac{1}{|G|}\sum_{g \in G} t_1^{j_1(g)}  t_2^{j_2(g)} \cdots t_n^{j_n(g)}</math>

де <math>n</math> є число елементів <math>X</math> та <math> j_k(g)</math> є число k-циклу групового елемента <math>g</math> в якості перестановки <math>X</math>.

Кольорова композиція&nbsp;— це орбіта дії <math>G</math> на множині <math>Y^X</math> (де <math>Y
</math> є набір кольорів, та <math>Y^X</math> позначає сукупність всіх функцій <math>\varphi: X \longrightarrow Y</math>). Вага такого пристрою визначається як сума ваг <math>\varphi(x)</math> за всіма <math>x \in X</math>. Теорема стверджує, що породжувальна функція <math>F</math> кількості кольорових компонентів з вагою визначається:

<math>F(t) = Z_G(f(t),f(t^2),f(t^3),\ldots,f(t^n))</math>

або в багатомірному випадку:

<math>F(t_1,t_2,\ldots) = Z_G(f(t_1,t_2,\ldots),f(t_1^2,t_2^2,\ldots),f(t_1^3,t_2^3,\ldots),\ldots,f(t_1^n,t_2^n,\ldots)).</math>

Щоб зменшити до спрощеної версії, наведеної раніше, якщо є <math>m
</math> кольорів, і всі мають вагу <math>0
</math>, то <math>f(t)=m 
</math> та <math>|Y^X/G| =F(0)= Z_G(m,m,\ldots,m)= \frac{1}{|G|}\sum_{g \in G} m^{c(g)}.
</math>

У знаменитому застосуванні лічильників дерев (див. Нижче) та ациклічних молекул, розташування «кольорових кульок» насправді є розташуванням домовленостей, таких як гілки кореневого дерева. Таким чином, твірна функція <math>f
</math> для кольорів походить від твірної функції <math>F
</math> для механізмів, а теорема перерахування Поя стає рекурсивною формулою.

== Приклади&nbsp; ==

=== Кольорові куби ===
Скільки способів кольорувати сторони тривимірного куба з m кольорами, аж до обертання куба? Група обертання C куба діє на шести сторонах куба, які еквівалентні намистинкам. Індекс циклу&nbsp;— це

<math>Z_C(t_1,t_2,t_3,t_4) = \frac{1}{24}\left(t_1^6 + 6 t_1^2 t_4 + 3 t_1^2 t_2^2 + 8 t_3^2 + 6 t_2^3\right)
</math>

яка отримується шляхом аналізу дії кожного з 24 елементів C на 6 сторін куба, див. тут для подробиць.

Ми беремо всі кольори, щоб мати вагу 0 і виявити, що є

<math>F(0)=Z_C(m,m,m,m) = \frac{1}{24}\left(m^6+ 3m^4 + 12 m^3 + 8 m^2\right)
</math>

різні фарби.

=== Графи з трьома та чотирма вершинами ===

Граф на <math>m</math> вершинах можна інтерпретувати як розташування кольорових кульок. Набір <math>X</math> «намистин»&nbsp;— це сукупність <math>\binom{m}2</math> можливих ребер, а набір кольорів <math>Y = \{black,white\}</math> відповідає наявним (чорним) або відсутнім (білим) ребрам. Теорія перерахування Поя може бути використана для обчислення кількості графів з точністю до [[Ізоморфізм графів|ізоморфізму]] з фіксованим числом вершин або функції породження цих графів за кількістю їхніх ребер. Для останньої задачи можна сказати, що чорне, тобто, присутнє ребро має вагу 1, тоді як відсутнє або біле ребро має вагу 0. Таким чином, <math>f(t) = 1+t</math> є твірною функцією для набору кольорів. Відповідна група симетрії&nbsp;— це <math>G = S_m</math>, [[симетрична група]] на m букв. Ця група діє на множині <math>X</math> можливих ребер: перестановка φ ребру <math> \{a,b\}</math> ставить у відповідність ребро <math>\{\varphi(a),\varphi(b)\}</math>. За допомогою цих визначень клас ізоморфних графів з <math>m</math> вершинами буде такий самий, як орбіта дії <math>G</math> на множині <math>Y^X</math> кольорових компонентів; кількість ребер графу дорівнює вазі розташування.

[[Image:AllGraphsOnThreeVertices.png|thumb|All graphs on three vertices]]
[[Image:NonisomorphicGraphsOnThreeVertices.png|thumb|Nonisomorphic graphs on three vertices]]

Вісім графіків на трьох вершинах (перед виявленням ізоморфних графів) показано справа. Існує чотири класи графіків ізоморфізму, також показані справа.

Індекс циклу групи <math>S_3</math>, що діє на безліч трьох ребер, є
: <math>Z_G(t_1,t_2,t_3) = \frac{1}{6}\left(t_1^3 + 3 t_1 t_2 + 2 t_3\right)</math>
Таким чином, згідно з теоремою про перерахування, породжуюча функція графів на 3 вершинах з точністю до ізоморфізму буде
: <math>F(t) = Z_G(t+1,t^2+1,t^3+1) = \frac{1}{6}\left((t+1)^3 + 3 (t+1) (t^2+1) + 2 (t^3+1)\right),</math>
яка спрощується до 
: <math>F(t) = t^3+t^2+t+1.</math>
Таким чином, є лише один граф з кількістю ребер від 0 до 3.


Індекс циклу групи <math>S_4</math>, що діє на множині з 6 ребер

<math>
Z_G(t_1,t_2,t_3,t_4) = \frac{1}{24}\left(t_1^6 + 9 t_1^2 t_2^2 + 8 t_3^2 + 6 t_2 t_4\right)
</math>

Отже

<math>
F(t) = Z_G(t+1,t^2+1,t^3+1,t^4+1) = \frac{(t+1)^6 + 9 (t+1)^2 (t^2+1)^2 + 8 (t^3+1)^2 + 6 (t^2+1) (t^4+1)}{24}
</math>

що спрощує

<math>F(t) = t^6 + t^5 + 2 t^4 + 3 t^3 + 2 t^2 + t + 1.</math>

=== Кореневі трійкові дерева ===
{{Докладніше|Трійкове дерево}}
Набір <math>T_3</math> з кореневих [[Трійкове дерево|трійкових дерев]] складається з кореневих дерев, де кожен вузол (або нелітакова вершина) містить рівно трьох дітей (листя або підроди). Малі трійкові дерева показані справа. Зверніть увагу, що кореневі трійкові дерева з <math>n</math> вузлами еквівалентні кореневим деревам з <math>n</math> вершинами ступеня не більше 3 (ігноруючи листя). Взагалі, дві кореневі дерева є ізоморфними, коли їх можна одержувати з іншого, переміщуючи дітей своїх вузлів. Іншими словами, група, яка діє на дітей вузла, є симетричною групою <math>S_3</math>. Ми визначаємо вагу такого трійкового дерева як кількість вузлів (або вершини без листа).

Ви можете побачити кореневе, трійкове дерево як рекурсивний об'єкт, який є або листком, або вузлом із трьома дітьми, які самі по собі є трійковими деревами. Ці діти еквівалентні бісеру; індекс циклу симетричної групи <math>S_3</math>, що діє на них, є

<math>Z_{{S_{3}}}(t_{1},t_{2},t_{3})={\frac  {t_{1}^{3}+3t_{1}t_{2}+2t_{3}}{6}}.</math>

Теорема про перерахування Поя перетворює рекурсивну структуру кореневих трійкових дерев на функціональне рівняння для батьківської функції <math>F(t)</math>кореневих трійкових дерев за кількістю вузлів. Це досягається шляхом «розмальовування» трьох дітей із кореневими трійковими деревами, зваженими за номером вузла, так що функція генерації кольорів дається

<math>f(t)=F(t)</math>

що дає теорема про перерахування

<math>
\frac{F(t)^3 + 3 F(t)F(t^2) + 2 F(t^3)}{6}
</math>

Це еквівалентно такій формулі повторення для числа <math>t_n</math> кореневих трійкових дерев з <math>n</math> вузлами: де <math>a,b</math> та <math>c</math>&nbsp;— це невід'ємні цілі числа.

Перші кілька значень <math>t_n</math> є

1, 1, 1, 2, 4, 8, 17, 39, 89, 211, 507, 1238, 3057, 7639, 19241 (послідовність [[A000598]] в [[Енциклопедія послідовностей цілих чисел|OEIS]])

== Доведення теореми  ==

Спрощена форма теореми про перерахування Поя випливає з леми Бернсайда, яка говорить, що кількість орбіт фарбування є середнім числом елементів <math>Y^X</math> фіксована перестановка <math>g</math> з <math>G</math> за всіма перестановок <math>g</math>. Зважена версія теореми має схоже доведення, але з формою леми Бернсайда для зваженого перерахунку. Це еквівалентно застосуванню леми Бернсайда окремо на орбітах різної ваги.

Для чіткішого позначення, позначимо <math>
 {\displaystyle x_{1},x_{2},\ldots } x_{1},x_{2},\ldots </math> змінними твірної функції <math>f</math> від <math>Y</math>. Враховуючи вектор ваг <math>\omega </math>, позначимо <math> x^{\omega }</math> відповідний мономаначний член <math>f</math>. Застосування леми Бернсайда до орбіт дій ваги <math>\omega</math>, число орбіт дій цієї ваги є:

<math>
{\frac  {1}{|G|}}\sum _{{g\in G}}|(Y^{X})_{{\omega ,g}}|
</math>

де <math>
 {\displaystyle (Y^{X})_{\omega ,g}} 
</math> це набір кольорів ваги <math>\omega </math> які також фіксуються <math>g</math>. Якщо ми підсумовуємо всі можливі ваги, отримаємо

<math>
F(x_{1},x_{2},\ldots )={\frac  {1}{|G|}}\sum _{{g\in G,\omega }}x^{\omega }|(Y^{X})_{{\omega ,g}}|.
</math>

Тим часом груповий елемент <math>g</math> із структурою циклу <math>
 j_1(g),j_2(g),\ldots,j_n(g)
</math> буде

<math>
t_{1}^{{j_{1}(g)}}t_{2}^{{j_{2}(g)}}\cdots t_{n}^{{j_{n}(g)}}
</math>

до індексу циклу <math>G</math>. Елемент <math>g</math> фіксує елемент <math>\varphi</math> з <math>Y ^ X</math> тоді і тільки тоді, коли функція <math>\varphi</math> постійна на кожному циклі <math>q </math> групи <math>g</math>. Для кожного такого циклу

<math>q </math> виробляюча функція за масою <math>|q |</math> ідентичні кольори з набору, переліченого <math>f</math>, є

<math>
f(x_{1}^{{|q|}},x_{2}^{{|q|}},x_{3}^{{|q|}},\ldots ).
</math>

Звідси випливає, що функція, що породжує, за масою точок, фіксованих <math>g</math>, є підсумком зазначеного вище терміну по всіх циклах <math>g
</math>, тобто

<math>
\sum_{\omega} x^\omega |(Y^X)_{\omega,g}| = \prod_{q \text{ cycle of } g} f(x_1^{|q|}, x_2^{|q|}, x_3^{|q|}, \ldots),
</math>

що дорівнює

<math>
f(x_{1},x_{2},\ldots )^{{j_{1}(g)}}f(x_{1}^{2},x_{2}^{2},\ldots )^{{j_{2}(g)}}\cdots f(x_{1}^{n},x_{2}^{n},\ldots )^{{j_{n}(g)}}.
</math>

Підставляти це для <math>
 {\displaystyle \sum _{\omega }x^{\omega }|(Y^{X})_{\omega ,g}|} 
</math> у сумі над усіма <math>
g
</math> дає індекс заміщеного циклу як заявлено.

== Примітки ==
{{reflist}}

== Посилання ==
* {{cite journal
 |last=Redfield|first=J. Howard|title=The Theory of Group-Reduced Distributions|url=https://archive.org/details/sim_american-journal-of-mathematics_1927-07_49_3/page/433|journal=[[American Journal of Mathematics]]|volume=49|year=1927|issue=3|pages=433–455|doi=10.2307/2370675|mr=1506633|jstor=2370675}}
* {{cite journal
 |author=[[Френк Харарі|Frank Harary]]|author2=Ed Palmer|title=The Enumeration Methods of Redfield|url=https://archive.org/details/sim_american-journal-of-mathematics_1967-04_89_2/page/373|journal=[[American Journal of Mathematics]]|volume=89|year=1967|issue=2|pages=373–384|doi=10.2307/2373127|mr=0214487|jstor=2373127}}
* {{cite journal|author=G. Pólya|title=Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen|journal=[[Acta Mathematica]]|volume=68|year=1937|issue=1|pages=145–254|url=http://www.springerlink.com/content/9021012252111875/|doi=10.1007/BF02546665}}{{Недоступне посилання}}
* {{cite book|title=Combinatorial Enumeration of Groups, Graphs, and Chemical Compounds|mr=0884155|author=G. Pólya|author2=R. C. Read|publisher=[[Springer-Verlag]]|location=New York|date=1987|isbn=0-387-96413-4|url-access=registration|url=https://archive.org/details/combinatorialenu0000poly}}
* [http://demonstrations.wolfram.com/ApplyingThePolyaBurnsideEnumerationTheorem/ Applying the Pólya-Burnside Enumeration Theorem] {{Webarchive|url=https://web.archive.org/web/20191011050416/http://demonstrations.wolfram.com/ApplyingThePolyaBurnsideEnumerationTheorem/ |date=11 жовтня 2019 }} by Hector Zenil and Oleksandr Pavlyk, [[The Wolfram Demonstrations Project]].
* {{MathWorld |title=Polya Enumeration Theorem|urlname=PolyaEnumerationTheorem}}
* Frederic Chyzak [http://algo.inria.fr/libraries/autocomb/Polya-html/Polya.html Enumerating alcohols and other classes of chemical molecules, an example of Pólya theory] {{Webarchive|url=https://web.archive.org/web/20080511104847/http://algo.inria.fr/libraries/autocomb/Polya-html/Polya.html |date=11 травня 2008 }}.

{{ВП-портали|Математика|Хімія|Природничі науки}}

[[Категорія:Математичні теореми]]