Redfield-Poyi teorem

Redfield-Polyi-sætningen (teori) er et klassisk resultat af enumerativ kombinatorik .

Historie

Denne teorem blev først opnået og offentliggjort af Redfieldi 1927 , men arbejdet blev betragtet som meget specielt og gik ubemærket hen. Poya beviste uafhængigt det samme i 1937 , men han viste sig at være en meget mere succesfuld popularisator - for eksempel viste han i sin første publikation anvendeligheden af dette resultat til opregning af kemiske forbindelser [1] .

Indledende definitioner

Lad to endelige mængder blive givet , samt en vægtfunktion . Lad . Uden tab af almenhed kan vi antage, at . $x$ $Y$ $w:Y\rightarrow \mathbb {N}$ $n=|X|$ $X=\{1,2,\ldots ,n\}$

Overvej et sæt funktioner . I dette tilfælde er funktionens vægt defineret som $F=\{f\midt f:X\højrepil Y\}$ $f$

w(f)=\sum _{x\in X}w\venstre(f(x)\højre)

Lad en undergruppe af den symmetriske gruppe virke på sættet . Lad os introducere et ækvivalensforhold vedr $x$ $EN$ $S_{n}$ $F$

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

for nogle .

a\i A

Ækvivalensklassen vil blive betegnet med og vil blive kaldt en kredsløb . Da vægtene af ækvivalente funktioner er de samme, kan vi definere vægten af kredsløbet som . $f$ $[f]$ $f$ $w([f])=w(f)$

Lade

c_{k}=\venstre|\{y\in Y\midt w(y)=k\}\right|

er antallet af vægtelementer ;

Y

k

C_{k}=\venstre|\{[f]\midt w([f])=k\}\højre|

er antallet af vægtbaner ;

k

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

og er de tilsvarende genereringsfunktioner .

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

Cyklisk indeks

Det cykliske indeks for en undergruppe af en symmetrisk gruppe er defineret som et polynomium i variable $EN$ $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)},

hvor er antallet af længdecyklusser i permutationen . $j_{k}(a)$ $k$ $-en$

Redfield-Poyi-sætningen

Redfield-Poyi- sætningen siger det

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

hvor er det cykliske indeks for gruppen [2] [3] . $Z_{A}$ $EN$

Beviset for Redfield-Polyi-sætningen er baseret på Burnsides lemma [4] [5] .

Der er talrige generaliseringer af Redfield-Polyi-sætningen [6] .

Applikationseksempler

Problemet med antallet af halskæder

En opgave. Find antallet af halskæder, der består af perler i to farver. Halskæder, der matcher, når de drejes, betragtes som de samme (flip er ikke tilladt). $n$

Løsning. Lad sættet svare til numrene på perlerne i halskæden, og vær sættet af mulige farver. Vi indstiller vægtfunktionen ens for alle . Sættet har et element med vægt 0 og et element med vægt 1, det vil sige og . Hvor . $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$

Lad være sættet af alle funktioner fra til . Enhver funktion definerer en eller anden halskæde, og omvendt er hver halskæde defineret af en eller anden funktion fra . I dette tilfælde er vægten af funktionen lig med antallet af perler af farve 1 i den tilsvarende halskæde. $F=\{f\midt f:X\to Y\}$ $x$ $Y$ $f\in F$ $F$

Rotationsgruppen genereret af den cykliske permutation virker på mængden , som definerer en ækvivalensrelation på . Så vil halskæder, der falder sammen, når de drejer, nøjagtigt svare til tilsvarende funktioner, og problemet reduceres til at tælle antallet af baner. $x$ $EN$ $(1,2,\ldots,n)$ $F$

Gruppens cykliske indeks er $EN$

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

hvor er Euler funktion , er den største fælles divisor af tal og . $\varphi (d)$ $(k,n)$ $k$ $n$

Ifølge Redfield-Polyi-sætningen,

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

Antallet af vægtbaner (det vil sige forskellige halskæder med perler af farve 1 ) er lig 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 samlede antal forskellige baner (eller halskæder) er

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

Noter

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

Litteratur

Enumerative problemer med kombinatorisk analyse / Samling af oversættelser redigeret af G. P. Gavrilov. — M .: Mir, 1979.
Kombinatorisk anvendt matematik / Ed. E. Beckenbach. — M .: Mir, 1968.
Kaluznin L. A., Sushchansky V. I. Transformationer og permutationer. — M.: Nauka, 1985.
Harari F. Grafteori. — M .: Mir, 1973.
Harari F., Palmer E. Grafopregning. — M .: Mir, 1977.
Yakovenko D. I. Problemet med halskæder // Bulletin fra Omsk University. - 1998. - Udgave. 2 . - S. 21-24 . Arkiveret fra originalen den 8. maj 2005.
Rybnikov K. A. Introduktion til kombinatorisk analyse. - M. : MGU, 1972. - 253 s.
Nefedov V. N., Osipova V. A. Kursus i diskret matematik. - M. : MAI, 1992. - 262 s.