Teorema Redfield-Poyi

Teorema Redfield-Polyi (teoria) este un rezultat clasic al combinatoriei enumerative .

Istorie

Această teoremă a fost obținută și publicată pentru prima dată de Redfieldîn 1927 , dar lucrarea a fost considerată deosebită și a trecut neobservată. Poya a dovedit în mod independent același lucru în 1937 , dar s-a dovedit a fi un popularizator mult mai de succes - de exemplu, în prima sa publicație, a arătat aplicabilitatea acestui rezultat la enumerarea compușilor chimici [1] .

Definiții introductive

Să fie date două mulţimi finite şi , precum şi o funcţie de greutate . Lasă . Fără a pierde generalitatea, putem presupune că . $X$ $Y$ $w:Y\rightarrow \mathbb {N}$ $n=|X|$ $X=\{1,2,\ldots ,n\}$

Luați în considerare un set de funcții . În acest caz, ponderea funcției este definită ca $F=\{f\mid f:X\rightarrow Y\}$ $f$

w(f)=\sum _{x\in X}w\left(f(x)\dreapta)

Fie ca un subgrup al grupului simetric să acționeze asupra mulțimii . Să introducem o relație de echivalență pe $X$ $A$ $S_{n}$ $F$

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

pentru unii .

a\în A

Clasa de echivalență va fi notă și va fi numită orbită . Deoarece ponderile funcțiilor echivalente sunt aceleași, putem defini greutatea orbitei ca . $f$ $[f]$ $f$ $w([f])=w(f)$

Lăsa

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

este numărul de elemente de greutate ;

Y

k

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

este numărul de orbite de greutate ;

k

c(t)=\sum _{k}c_{k}\cdot t^{k}

și sunt funcțiile generatoare corespunzătoare .

C(t)=\sum _{k}C_{k}\cdot t^{k}

Indicele ciclic

Indicele ciclic al unui subgrup al unui grup simetric este definit ca un polinom în variabile $A$ $S_{n}$ $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)},

unde este numărul de cicluri de lungime din permutare . $j_{k}(a)$ $k$ $A$

Teorema Redfield-Poyi

Teorema Redfield-Poyi afirmă că

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

unde este indicele ciclic al grupului [2] [3] . $Z_{A}$ $A$

Dovada teoremei Redfield-Polyi se bazează pe lema lui Burnside [4] [5] .

Există numeroase generalizări ale teoremei Redfield-Polyi [6] .

Exemple de aplicații

Problema numărului de coliere

O sarcină. Găsiți numărul de coliere formate din margele de două culori. Colierele care se potrivesc atunci când sunt rotite sunt considerate la fel (nu sunt permise răsturnări). $n$

Soluţie. Lasă setul să corespundă numerelor margelelor din colier și să fie setul de culori posibile. Setăm funcția de greutate egală pentru toate . Setul are un element de greutate 0 și un element de greutate 1, adică și . Unde . $X=\{1,2,\ldots ,n\}$ $Y=\{0,1\}$ $w(y)=y$ $y\în Y$ $Y$ $c_{0}=1$ $c_{1}=1$ $c(t)=1+t$

Fie setul tuturor funcțiilor de la până la . Orice funcție definește un colier și, invers, fiecare colier este definit de o funcție de la . În acest caz, greutatea funcției este egală cu numărul de margele de culoare 1 din colierul corespunzător. $F=\{f\mid f:X\la Y\}$ $X$ $Y$ $f\in F$ $F$

Grupul de rotație generat de permutarea ciclică acționează asupra mulțimii , care definește o relație de echivalență pe . Apoi, colierele care coincid la întoarcere vor corespunde exact cu funcții echivalente, iar problema se reduce la numărarea numărului de orbite. $X$ $A$ $(1,2,\ldots ,n)$ $F$

Indicele ciclic al grupului este $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}\varphi (n/d)t_{n/d}^{d}= {\frac {1}{n}}\sum _{d|n}\varphi (d)t_{d}^{n/d},

unde este funcția Euler , este cel mai mare divizor comun al numerelor și . $\varphi (d)$ $(k,n)$ $k$ $n$

Conform teoremei Redfield-Polyi,

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

Numărul de orbite de greutate (adică diferite coliere cu margele de culoare 1 ) este egal cu coeficientul at în : $k$ $k$ $C_{k}$ $t^{k}$ $CT)$

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

Numărul total de orbite diferite (sau coliere) este

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

Note

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

Literatură

Probleme enumerative de analiză combinatorie / Culegere de traduceri editată de G. P. Gavrilov. — M .: Mir, 1979.
Matematică aplicată combinatorie / Ed. E. Beckenbach. — M .: Mir, 1968.
Kaluznin L. A., Sushchansky V. I. Transformări și permutări. — M.: Nauka, 1985.
Harari F. Teoria grafurilor. — M .: Mir, 1973.
Harari F., Palmer E. Enumerarea grafică. — M .: Mir, 1977.
Yakovenko D. I. Problema colierelor // Buletinul Universității din Omsk. - 1998. - Emisiune. 2 . - S. 21-24 . Arhivat din original pe 8 mai 2005.
Rybnikov K. A. Introducere în analiza combinatorie. - M. : MGU, 1972. - 253 p.
Nefedov V. N., Osipova V. A. Curs de matematică discretă. - M. : MAI, 1992. - 262 p.