Теорема перерахування Поя

Теорема перерахування Поя, також відома як теорема Редфілда-Поя, теорема в комбінаториці, що випливає з та узагальнює лему Бернсайда про кількість орбіт дії групи на множині. Теорему вперше було опубліковано Джоном Говардом Редфілдом у 1927 році. У 1937 році вона була незалежно наново доведена Дьордем Поя, який потім значно популяризував результат, застосовуючи його до багатьох лічильних задач, зокрема до переліку хімічних сполук.

Теорему перерахування Поя може бути включено до символьних методів комбінаторики та до комбінаторних видів.

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

Нехай $X$ скінченна множина, та $G$ є групою перестановок з $X$ (або скінченною групою симетрій, яка діє на $X$). Множина X може бути кінцевою множиною кульок, а $G$ може бути обраною групою перестановок кульок. Наприклад, якщо $X$ є намисто з $n$ кульок, то важлива поворотна симетрія, так що $G$ є циклічною групою $C_{n}$, в той час як, якщо $X$ є намистом, а повороти та відображення мають відношення, так що $G$ — діедральна група $D_{n}$ порядку $2n$.

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

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

$|Y^{X}/G|={\frac {1}{|G|}}\sum _{g\in G}m^{c(g)},$

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

Повна, зважена версія

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

$f(t)=f_{0}+f_{1}t+f_{2}t^{2}+...$

є твірною функцією набору кольорів, тож існує $f_{w}$ кольорів ваги $w$ для кожного цілого $w\geq 0$. У багатоваріантному випадку вага кожного кольору є вектором цілих чисел і є батьківська функція $f(t1,t2,...)$, яка табулює кількість кольорів із кожним уведеним важелем. Теорія перерахунку використовує іншу багатомірну твірну функцію, яка називається індексом циклу :

$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)}$

де $n$ є число елементів $X$ та $j_{k}(g)$ є число k-циклу групового елемента $g$ в якості перестановки $X$.

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

$F(t)=Z_{G}(f(t),f(t^{2}),f(t^{3}),\ldots ,f(t^{n}))$

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

$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 )).$

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

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

Приклади 

Кольорові куби

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

$Z_{C}(t_{1},t_{2},t_{3},t_{4})={\frac {1}{24}}\left(t_{1}^{6}+6t_{1}^{2}t_{4}+3t_{1}^{2}t_{2}^{2}+8t_{3}^{2}+6t_{2}^{3}\right)$

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

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

$F(0)=Z_{C}(m,m,m,m)={\frac {1}{24}}\left(m^{6}+3m^{4}+12m^{3}+8m^{2}\right)$

різні фарби.

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

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

Файл:AllGraphsOnThreeVertices.png

All graphs on three vertices

Файл:NonisomorphicGraphsOnThreeVertices.png

Nonisomorphic graphs on three vertices

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

Індекс циклу групи $S_{3}$, що діє на безліч трьох ребер, є

$Z_{G}(t_{1},t_{2},t_{3})={\frac {1}{6}}\left(t_{1}^{3}+3t_{1}t_{2}+2t_{3}\right)$

Таким чином, згідно з теоремою про перерахування, породжуюча функція графів на 3 вершинах з точністю до ізоморфізму буде

$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),$

яка спрощується до

$F(t)=t^{3}+t^{2}+t+1.$

Таким чином, є лише один граф з кількістю ребер від 0 до 3.

Індекс циклу групи $S_{4}$, що діє на множині з 6 ребер

$Z_{G}(t_{1},t_{2},t_{3},t_{4})={\frac {1}{24}}\left(t_{1}^{6}+9t_{1}^{2}t_{2}^{2}+8t_{3}^{2}+6t_{2}t_{4}\right)$

Отже

$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}}$

що спрощує

$F(t)=t^{6}+t^{5}+2t^{4}+3t^{3}+2t^{2}+t+1.$

Кореневі трійкові дерева

Набір $T_{3}$ з кореневих трійкових дерев складається з кореневих дерев, де кожен вузол (або нелітакова вершина) містить рівно трьох дітей (листя або підроди). Малі трійкові дерева показані справа. Зверніть увагу, що кореневі трійкові дерева з $n$ вузлами еквівалентні кореневим деревам з $n$ вершинами ступеня не більше 3 (ігноруючи листя). Взагалі, дві кореневі дерева є ізоморфними, коли їх можна одержувати з іншого, переміщуючи дітей своїх вузлів. Іншими словами, група, яка діє на дітей вузла, є симетричною групою $S_{3}$. Ми визначаємо вагу такого трійкового дерева як кількість вузлів (або вершини без листа).

Ви можете побачити кореневе, трійкове дерево як рекурсивний об'єкт, який є або листком, або вузлом із трьома дітьми, які самі по собі є трійковими деревами. Ці діти еквівалентні бісеру; індекс циклу симетричної групи $S_{3}$, що діє на них, є

$Z_{S_{3}}(t_{1},t_{2},t_{3})={\frac {t_{1}^{3}+3t_{1}t_{2}+2t_{3}}{6}}.$

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

$f(t)=F(t)$

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

${\frac {F(t)^{3}+3F(t)F(t^{2})+2F(t^{3})}{6}}$

Це еквівалентно такій формулі повторення для числа $t_{n}$ кореневих трійкових дерев з $n$ вузлами: де $a,b$ та $c$ — це невід'ємні цілі числа.

Перші кілька значень $t_{n}$ є

1, 1, 1, 2, 4, 8, 17, 39, 89, 211, 507, 1238, 3057, 7639, 19241 (послідовність A000598 в OEIS)

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

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

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

${\frac {1}{|G|}}\sum _{g\in G}|(Y^{X})_{\omega ,g}|$

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

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

Тим часом груповий елемент $g$ із структурою циклу $j_{1}(g),j_{2}(g),\ldots ,j_{n}(g)$ буде

$t_{1}^{j_{1}(g)}t_{2}^{j_{2}(g)}\cdots t_{n}^{j_{n}(g)}$

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

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

$f(x_{1}^{|q|},x_{2}^{|q|},x_{3}^{|q|},\ldots ).$

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

$\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 ),$

що дорівнює

$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)}.$

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

Посилання

• Redfield, J. Howard (1927). The Theory of Group-Reduced Distributions. American Journal of Mathematics. 49 (3): 433—455. doi:10.2307/2370675. JSTOR 2370675. MR 1506633.
• Frank Harary; Ed Palmer (1967). The Enumeration Methods of Redfield. American Journal of Mathematics. 89 (2): 373—384. doi:10.2307/2373127. JSTOR 2373127. MR 0214487.
• G. Pólya (1937). Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen. Acta Mathematica. 68 (1): 145—254. doi:10.1007/BF02546665.^{[недоступне посилання]}
• G. Pólya; R. C. Read (1987). Combinatorial Enumeration of Groups, Graphs, and Chemical Compounds. New York: Springer-Verlag. ISBN 0-387-96413-4. MR 0884155.
• Applying the Pólya-Burnside Enumeration Theorem [Архівовано 11 жовтня 2019 у Wayback Machine.] by Hector Zenil and Oleksandr Pavlyk, The Wolfram Demonstrations Project.
• Weisstein, Eric W. Polya Enumeration Theorem(англ.) на сайті Wolfram MathWorld.
• Frederic Chyzak Enumerating alcohols and other classes of chemical molecules, an example of Pólya theory [Архівовано 11 травня 2008 у Wayback Machine.].