Redfieldova-Poyiho věta

Redfield-Polyiho teorém (teorie) je klasickým výsledkem enumerativní kombinatoriky .

Historie

Tuto větu poprvé získal a publikoval Redfieldv roce 1927 , ale dílo bylo považováno za velmi zvláštní a zůstalo bez povšimnutí. Poya nezávisle prokázal totéž v roce 1937 , ale ukázal se jako mnohem úspěšnější popularizátor - například ve své první publikaci ukázal použitelnost tohoto výsledku na výčet chemických sloučenin [1] .

Úvodní definice

Nechť jsou dány dvě konečné množiny a , stejně jako váhová funkce . Nechte _ Bez ztráty obecnosti můžeme předpokládat, že . $X$ $Y$ $w:Y\rightarrow \mathbb {N}$ $n=|X|$ $X=\{1,2,\ldots ,n\}$

Zvažte sadu funkcí . V tomto případě je váha funkce definována jako $F=\{f\mid f:X\rightarrow Y\}$ $F$

w(f)=\součet _{x\in X}w\left(f(x)\vpravo)

Nechť některá podgrupa symetrické grupy působí na množinu . Zaveďme vztah ekvivalence na $X$ $A$ $S_{n}$ $F$

f\sim g\quad \Longleftrightarrow \quad f=g\circ a

pro některé .

v A

Třída ekvivalence bude označena a bude nazývána orbita . Protože váhy ekvivalentních funkcí jsou stejné, můžeme definovat váhu orbity jako . $F$ $[F]$ $F$ $w([f])=w(f)$

Nechat

c_{k}=\left|\{y\in Y\mid w(y)=k\}\right|

je počet prvků hmotnosti ;

Y

k

C_{k}=\left|\{[f]\mid w([f])=k\}\right|

je počet oběžných drah hmotnosti ;

k

c(t)=\součet _{k}c_{k}\cdot t^{k}

a jsou odpovídajícími generujícími funkcemi .

C(t)=\součet _{k}C_{k}\cdot t^{k}

Cyklický index

Cyklický index podskupiny symetrické skupiny je definován jako polynom v proměnných $A$ $S_{n}$ $n$ $t_{1},t_{2},\ldots ,t_{n}$

Z_{A}(t_{1},t_{2},\ldots ,t_{n})={\frac {1}{|A|}}\součet _{a\in A}t_{1}^ {j_{1}(a)}\cdot t_{2}^{j_{2}(a)}\cdot \ldots \cdot t_{n}^{j_{n}(a)},

kde je počet cyklů délky v permutaci . $j_{k}(a)$ $k$ $A$

Redfieldova-Poyiho věta

Říká to Redfield-Poyiho teorém

C(t)=Z_{A}{\big (}c(t),c(t^{2}),\ldots ,c(t^{n}){\big )},

kde je cyklický index grupy [2] [3] . $Z_{A}$ $A$

Důkaz Redfield-Polyiho teorému je založen na Burnsideově lematu [4] [5] .

Existuje mnoho zobecnění Redfield-Polyiho teorému [6] .

Příklady aplikací

Problém počtu náhrdelníků

Úkol. Najděte počet náhrdelníků složených z korálků dvou barev. Náhrdelníky, které se při otočení shodují, jsou považovány za stejné (převrácení není povoleno). $n$

Řešení. Nechť sada odpovídá číslům korálků v náhrdelníku a je sadou možných barev. Váhovou funkci nastavíme stejnou pro všechny . Sada má jeden prvek o váze 0 a jeden prvek o váze 1, tedy a . kde . $X=\{1,2,\ldots ,n\}$ $Y=\{0,1\}$ $w(y)=y$ $y\v Y$ $Y$ $c_{0}=1$ $c_{1}=1$ $c(t)=1+t$

Nechť je množina všech funkcí od do . Jakákoli funkce definuje nějaký náhrdelník a naopak každý náhrdelník je definován nějakou funkcí z . V tomto případě je váha funkce rovna počtu korálků barvy 1 v odpovídajícím náhrdelníku. $F=\{f\mid f:X\to Y\}$ $X$ $Y$ $f\in F$ $F$

Rotační skupina generovaná cyklickou permutací působí na množinu , která definuje vztah ekvivalence na . Pak budou náhrdelníky, které se při otáčení shodují, přesně odpovídat ekvivalentním funkcím a problém se zmenší na počítání počtu oběhů. $X$ $A$ $(1,2,\ldots ,n)$ $F$

Cyklický index skupiny je $A$

Z_{A}(t_{1},\ldots ,t_{n})={\frac {1}{n))\sum _{k=1}^{n}t_{n/(k ,n)}^{(k,n)}={\frac {1}{n}}\součet _{d\mid n}\varphi (n/d)t_{n/d}^{d}= {\frac {1}{n}}\součet _{d|n}\varphi (d)t_{d}^{n/d},

kde je Eulerova funkce , je největší společný dělitel čísel a . $\varphi (d)$ $(k,n)$ $k$ $n$

Podle Redfield-Polyiho teorému,

C(t)=Z_{A}(1+t,1+t^{2},\ldots ,1+t^{n})={\frac {1}{n))\součet _ {d|n}\varphi (d)(1+t^{d})^{n/d}.

Počet oběžných drah hmotnosti (tj. různých náhrdelníků s korálky barvy 1 ) se rovná koeficientu at in : $k$ $k$ $C_{k}$ $t^{k}$ $C(t)$

C_{k}={\frac {1}{n}}\součet _{d|(n,k)}\varphi (d){\binom {n/d}{k/d}}.

Celkový počet různých orbit (nebo náhrdelníků) je

\sum _{k}C_{k}=C(1)={\frac {1}{n))\sum _{d|n}\varphi (d)2^{n/d}.

Poznámky

↑ Pólya G. Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen // Acta Mathematica . - 1937. - Sv. 68. - S. 145-254. - doi : 10.1007/BF02546665 .
↑ Nefedov, 1992 , str. 156.
↑ Rybnikov, 1972 , s. 71.
↑ Nefedov, 1992 , str. 157-159.
↑ Rybnikov, 1972 , s. 72-74.
↑ Rybnikov, 1972 , s. 74.

Literatura

Enumerativní problémy kombinatorické analýzy / Collection of translations edited by G. P. Gavrilov. — M .: Mir, 1979.
Kombinatorická aplikovaná matematika / Ed. E. Beckenbach. — M .: Mir, 1968.
Kalužnin L. A., Sushchansky V. I. Transformace a permutace. — M.: Nauka, 1985.
Harari F. Teorie grafů. — M .: Mir, 1973.
Harari F., Palmer E. Výčet grafů. — M .: Mir, 1977.
Jakovenko D. I. Problém náhrdelníků // Bulletin Omské univerzity. - 1998. - Vydání. 2 . - S. 21-24 . Archivováno z originálu 8. května 2005.
Rybnikov K. A. Úvod do kombinatorické analýzy. - M. : MGU, 1972. - 253 s.
Nefedov V. N., Osipova V. A. Kurz diskrétní matematiky. - M. : MAI, 1992. - 262 s.