Redfield-Poyi-lause

Redfield-Polyi-lause (teoria) on klassinen tulos numeratiivisesta kombinatoriikasta .

Historia

Tämän lauseen hankki ja julkaisi ensimmäisenä Redfieldvuonna 1927 , mutta työtä pidettiin erittäin erikoisena ja se jäi huomaamatta. Poya osoitti itsenäisesti saman asian vuonna 1937 , mutta hän osoittautui paljon menestyneemmäksi popularisoijaksi - esimerkiksi ensimmäisessä julkaisussaan hän osoitti tämän tuloksen soveltuvuuden kemiallisten yhdisteiden laskemiseen [1] .

Johdantomääritelmät

Olkoon kaksi äärellistä joukkoa ja annettu sekä painofunktio . Anna . Yleisyyttä menettämättä voimme olettaa, että . $X$ $Y$ $w:Y\rightarrow \mathbb {N}$ $n=|X|$ $X=\{1,2,\ldots ,n\}$

Harkitse joukkoa toimintoja . Tässä tapauksessa funktion paino määritellään seuraavasti $F=\{f\mid f:X\rightarrow Y\}$ $f$

w(f)=\summa _{x\in X}w\left(f(x)\oikea)

Toimikoon jokin symmetrisen ryhmän alaryhmä joukossa . Otetaan käyttöön ekvivalenssisuhde $X$ $A$ $S_{n}$ $F$

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

joillekin .

a\in A

Ekvivalenssiluokkaa merkitään ja sitä kutsutaan kiertoradalla . Koska vastaavien funktioiden painot ovat samat, voimme määritellä kiertoradan painoksi . $f$ $[f]$ $f$ $w([f])=w(f)$

Päästää

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

on painoelementtien lukumäärä ;

Y

k

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

on painoratojen lukumäärä ;

k

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

ja ovat vastaavat generointifunktiot .

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

Syklinen indeksi

Symmetrisen ryhmän aliryhmän syklinen indeksi määritellään muuttujien polynomiksi $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)},

missä on permutaatiossa olevien jaksojen lukumäärä . $j_{k}(a)$ $k$ $a$

Redfield-Poyi-lause

Redfield-Poyi- lause sanoo tämän

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

missä on ryhmän syklinen indeksi [2] [3] . $Z_{A}$ $A$

Redfield-Polyi-lauseen todistus perustuu Burnsiden lemmaan [4] [5] .

Redfield-Polyi-lauseesta on olemassa lukuisia yleistyksiä [6] .

Sovellusesimerkkejä

Kaulakorujen lukumäärän ongelma

Tehtävä. Etsi kaulakorujen määrä, jotka koostuvat kahden värin helmistä. Kierrettynä yhteensopivia kaulakoruja pidetään samanlaisina (käännät eivät ole sallittuja). $n$

Ratkaisu. Olkoon sarja vastaa kaulakorun helmien numeroita ja mahdollisten värien sarja. Asetamme painofunktion kaikille yhtäläiseksi . Joukko sisältää yhden painon 0 alkion ja yhden painon 1 elementin eli ja . Missä . $X=\{1,2,\ldots ,n\}$ $Y=\{0,1\}$ $w(y)=y$ $y\in Y$ $Y$ $c_{0}=1$ $c_{1}=1$ $c(t)=1+t$

Antaa olla joukko kaikki toiminnot alkaen ja . Mikä tahansa funktio määrittelee jonkin kaulakorun ja päinvastoin jokainen kaulakoru on määritelty jollakin funktiolla . Tässä tapauksessa funktion paino on yhtä suuri kuin vastaavan kaulakorun värin 1 helmien lukumäärä. $F=\{f\mid f:X\to Y\}$ $X$ $Y$ $f\in F$ $F$

Syklisen permutaation muodostama rotaatioryhmä vaikuttaa joukkoon , joka määrittelee ekvivalenssisuhteen . Tällöin käännettäessä osuvat kaulakorut vastaavat täsmälleen vastaavia toimintoja, ja ongelma rajoittuu kiertoratojen laskemiseen. $X$ $A$ $(1,2,\lpistettä ,n)$ $F$

Ryhmän syklinen indeksi on $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},

missä on Euler-funktio , on lukujen suurin yhteinen jakaja ja . $\varphi (d)$ $(k,n)$ $k$ $n$

Redfield-Polyi-lauseen mukaan

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

Painokierrosten lukumäärä (eli eri kaulakoruja, joissa on väriä 1 ) on yhtä suuri kuin kerroin at in : $k$ $k$ $C_{k}$ $t^{k}$ $C(t)$

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

Erilaisten kiertoratojen (tai kaulakorujen) kokonaismäärä on

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

Muistiinpanot

↑ Pólya G. Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen // Acta Mathematica . - 1937. - Voi. 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.

Kirjallisuus

Kombinatorisen analyysin numeratiiviset ongelmat / Käännöskokoelma, toimittanut G. P. Gavrilov. - M .: Mir, 1979.
Kombinatorinen sovellettu matematiikka / Toim. E. Beckenbach. - M .: Mir, 1968.
Kaluznin L. A., Sushchansky V. I. Transformaatiot ja permutaatiot. - M.: Nauka, 1985.
Harari F. Graafiteoria. - M .: Mir, 1973.
Harari F., Palmer E. Graph enumeration. - M .: Mir, 1977.
Yakovenko D. I. Kaulakorujen ongelma // Omskin yliopiston tiedote. - 1998. - Numero. 2 . - S. 21-24 . Arkistoitu alkuperäisestä 8. toukokuuta 2005.
Rybnikov K. A. Johdatus kombinatoriseen analyysiin. - M .: MGU, 1972. - 253 s.
Nefedov V. N., Osipova V. A. Diskreetin matematiikan kurssi. - M .: MAI, 1992. - 262 s.