Redfield-Poyi teorem

Redfield-Polyi-satsen (teorin) är ett klassiskt resultat av enumerativ kombinatorik .

Historik

Denna sats erhölls och publicerades först av Redfield1927 men verket ansågs mycket speciellt och gick obemärkt förbi . Poya bevisade självständigt samma sak 1937 , men han visade sig vara en mycket mer framgångsrik populariserare - till exempel visade han i sin första publikation att detta resultat är tillämpbart på uppräkningen av kemiska föreningar [1] .

Inledande definitioner

Låt två ändliga mängder och ges , samt en viktfunktion . Låt . Utan förlust av allmänhet kan vi anta att . $X$ $Y$ $w:Y\rightarrow \mathbb {N}$ $n=|X|$ $X=\{1,2,\ldots ,n\}$

Tänk på en uppsättning funktioner . I detta fall definieras funktionens vikt som $F=\{f\midt f:X\högerpil Y\}$ $f$

w(f)=\summa _{x\in X}w\left(f(x)\höger)

Låt någon undergrupp av den symmetriska gruppen agera på uppsättningen . Låt oss introducera ett ekvivalensförhållande på $X$ $A$ $S_{n}$ $F$

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

för vissa .

a\i A

Ekvivalensklassen kommer att betecknas med och kommer att kallas en omloppsbana . Eftersom vikterna för ekvivalenta funktioner är desamma kan vi definiera omloppsbanans vikt som . $f$ $[f]$ $f$ $w([f])=w(f)$

Låta

c_{k}=\vänster|\{y\in Y\mid w(y)=k\}\höger|

är antalet viktelement ;

Y

k

C_{k}=\vänster|\{[f]\mid w([f])=k\}\höger|

är antalet viktbanor ;

k

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

och är motsvarande genererande funktioner .

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

Cyklisk index

Det cykliska indexet för en undergrupp av en symmetrisk grupp definieras som ett polynom i variabler $A$ $S_{n}$ $n$ $t_{1},t_{2},\ldots ,t_{n}$

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

där är antalet längdcykler i permutationen . $j_{k}(a)$ $k$ $a$

Redfield-Poyi-satsen

Redfield-Poyi- satsen säger det

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

var är det cykliska indexet för gruppen [2] [3] . $Z_{A}$ $A$

Beviset för Redfield-Polyi-satsen är baserat på Burnsides lemma [4] [5] .

Det finns många generaliseringar av Redfield-Polyi-satsen [6] .

Applikationsexempel

Problemet med antalet halsband

En uppgift. Hitta antalet halsband som består av pärlor i två färger. Halsband som matchar när de roteras anses vara desamma (vändningar är inte tillåtna). $n$

Lösning. Låt uppsättningen motsvara numren på pärlorna i halsbandet, och vara uppsättningen av möjliga färger. Vi ställer in viktfunktionen lika för alla . Setet har ett element med vikt 0 och ett element med vikt 1, det vill säga och . Var . $X=\{1,2,\ldots ,n\}$ $Y=\{0,1\}$ $w(y)=y$ $y\i Y$ $Y$ $c_{0}=1$ $c_{1}=1$ $c(t)=1+t$

Låt vara uppsättningen av alla funktioner från till . Vilken funktion som helst definierar något halsband och, vice versa, varje halsband definieras av någon funktion från . I detta fall är funktionens vikt lika med antalet pärlor av färg 1 i motsvarande halsband. $F=\{f\mid f:X\to Y\}$ $X$ $Y$ $f\in F$ $F$

Rotationsgruppen som genereras av den cykliska permutationen verkar på mängden , som definierar en ekvivalensrelation på . Då kommer halsband som sammanfaller vid vändning exakt att motsvara likvärdiga funktioner, och problemet reduceras till att räkna antalet banor. $X$ $A$ $(1,2,\ldots,n)$ $F$

Det cykliska indexet för gruppen är $A$

Z_{A}(t_{1},\ldots ,t_{n})={\frac {1}{n))\summa _{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},

där är Euler-funktionen , är den största gemensamma delaren av tal och . $\varphi (d)$ $(k,n)$ $k$ $n$

Enligt Redfield-Polyi-satsen,

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

Antalet viktbanor (det vill säga olika halsband med pärlor av färg 1 ) är lika med koefficienten på i : $k$ $k$ $C_{k}$ $t^{k}$ $C(t)$

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

Det totala antalet olika banor (eller halsband) är

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

Anteckningar

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

Litteratur

Uppräkningsproblem av kombinatorisk analys / Samling av översättningar redigerad av G. P. Gavrilov. — M .: Mir, 1979.
Kombinatorisk tillämpad matematik / Ed. E. Beckenbach. — M .: Mir, 1968.
Kaluznin L. A., Sushchansky V. I. Transformationer och permutationer. — M.: Nauka, 1985.
Harari F. Grafteori. — M .: Mir, 1973.
Harari F., Palmer E. Grafuppräkning. — M .: Mir, 1977.
Yakovenko D. I. Problemet med halsband // Bulletin of the Omsk University. - 1998. - Utgåva. 2 . - S. 21-24 . Arkiverad från originalet den 8 maj 2005.
Rybnikov K. A. Introduktion till kombinatorisk analys. - M. : MGU, 1972. - 253 sid.
Nefedov V. N., Osipova V. A. Kurs i diskret matematik. - M. : MAI, 1992. - 262 sid.