Matematyka dyskretna 2/Wykład 5: Zastosowania teorii grup w zliczaniu

Kolorowanie zbioru $X$ to funkcja

$\omega :X⟶K,$

gdzie $K$ jest zbiorem kolorów.

Przykład

Rozważmy kolorowania naszyjnika złożonego z pięciu identycznych koralików $k_0,k_1,k_2,k_3,k_4$. Koraliki te mają takie same kształty i nie można ich rozróżnić. Możemy zatem zauważyć, że z jednego kolorowania ${\omega }_0$ da się utworzyć inne kolorowanie, nieodróżnialne od pierwszego, np. przez cykliczną zmianę numeracji koralików: ${\omega }_1\left(k_i\right)={\omega }_0\left(k_{(i-1mod5)}\right)$ jest nieodróżnialne od kolorowania ${\omega }_0\left(k_i\right)$. Przekształcenie indeksów $i-1mod5$ jest równoważne z obrotem o $72^{\circ }$.

[!h]

{poly_pieciokat} {Dwa kolorowania izomorficzne. [Rysunek z pliku: polypieciokat.eps]}

W ten sposób dostajemy $5$ kolorowań naszego naszyjnika. Ale, naszyjnik można też odwracać w rękach, lub -- co na jedno wychodzi -- spojrzeć na niego z drugiej strony. Mamy więc dodatkowe $5$ kolorowań naszego naszyjnika.

Zauważmy, ze w istocie każde $10$ z kolorowań możemy otrzymać z innego poprzez przekształcenie naszyjnika (pięciokąta) przez jakąś symetrię. Zbiór zmian ułożeń naszyjnika (permutacje jego koralików) wraz ze składaniem tych zmian (permutacji) tworzy więc grupę (w tym przypadku znaną nam już grupę dihedralną ${\mathbf{𝐃}}_5$ symetrii pięciokąta. W wykładzie tym poznamy metody zliczania tych kolorowań, które są odróżnialne.

G-zbiór to para $(\mathbf{𝐆},X)$, gdzie

• $X$ jest zbiorem skończonym,

• $\mathbf{𝐆}=(G,\circ )$ jest grupą permutacji zbioru $X$,

tzn. $G$ jest zamkniętym na składanie zbiorem permutacji zbioru $X$.

Czasem, dla G-zbioru $(\mathbf{𝐆},X)$ mówimy, ze grupa $\mathbf{𝐆}$ działa na zbiorze $X$.

Przykład

Rozważmy kwadrat o wierzchołkach $v_0,v_1,v_2,v_3$ oraz $4$ permutacje jego wierzchołków powstałe przez: odbicia względem przekątnych i obrót o $180^{\circ }$, tak jak zostało to pokazane na rysunku Uzupelnic pict square 1|.

[!h]

{poly_square_1} {Przekształcenia odpowiadające permutacjom $id,g_1,g_2,g_3$. [Rysunek z pliku: polysquare1.eps]}

Każde przedstawione przekształcenie geometryczne wyznacza jednoznacznie permutację zbioru indeksów wierzchołków kwadratu $X_{◻}=\{0,1,2,3\}$. Tak więc zbiór permutacji odpowiadających przekształceniom to $G_{◻}=\{id,g_1,g_2,g_3\}$. Przekształcenia $g_i$ można składać. Na przykład $g_1\circ g_2$ tworzy obrót o $180^{\circ }$ stopni, a więc $g_3$. Para $(G_{◻},\circ )$ tworzy grupę, więc $(G_{◻},X_{◻})$ jest przykładem G-zbioru, który jest opisany przez poniższe tabelki:

$\begin{array}{ccccc}j& 1& 2& 3& 4\\ HLINE\; TBDid(j)& 0& 1& 2& 3\\ g_1(j)& 0& 2& 1& 3\\ g_2(j)& 3& 1& 2& 0\\ g_3(j)& 3& 2& 1& 0\end{array}\begin{array}{ccccc}{g}_i\circ g_j& id& g_1& g_2& g_3\\ HLINE\; TBDid& id& g_1& g_2& g_3\\ g_1& g_1& id& g_3& g_2\\ g_2& g_2& g_3& id& g_1\\ g_3& g_3& g_2& g_1& id\end{array}$

Innymi słowy, grupa permutacji ${\mathbf{𝐆}}_{◻}$ działa na zbiorze $X_{◻}$.

Orbita $Gx$ elementu $x\in X$ w G-zbiorze $(G,X)$ to zbiór tych elementów zbioru $X$, które są postaci $g\left(x\right)$ dla pewnego $g\in G$, tzn.

$Gx=\{g\left(x\right)\in X:g\in G\}.$

Stabilizator $G_x$ elementu $x\in X$ w G-zbiorze $(G,X)$ to zbiór tych permutacji z $G$, które nie ruszają $x$ z miejsca, tzn.

$G_x=\{g\in G:g\left(x\right)=x\}.$

Ponadto zbiór permutacji przeprowadzających $x\in X$ w $y\in X$ oznaczamy przez

$G(x\to y)=\{g\in G:g\left(x\right)=y\}$

Przykład

Dla grupy $G_{◻}$ permutacji kwadratu z rysunku Uzupelnic pict square 1|, orbita oraz stabilizator elementu $0$ mają postać

$G_{◻}0=\{0,3\}{G}_{◻,0}=\{id,g_1\}.$

Mnożąc liczności obu tych zbiorów otrzymujemy liczbę elementów grupy $G_{◻}$, czyli innymi słowy $\left|G_{◻}0\right|\cdot \left|G_{◻,0}\right|=\left|G_{◻}\right|.$

Jako ćwiczenie [ex][ex equation between orbits] pozostawiamy dowód następującej obserwacji.

Obserwacja

Dla G-zbioru $(G,X)$ oraz $x,y\in X$ zachodzi

$\left|G_x\right|=\left|G(x\to y)\right|=\left|G(y\to x)\right|=\left|G_y\right|.$

Twierdzenie

Dla G-zbioru $(G,X)$ oraz $x\in X$ zachodzi

$\left|Gx\right|\cdot \left|G_x\right|=\left|G\right|.$

Dowód

Przy ustalonym $x\in X$ policzmy, na dwa różne sposoby, pary w zbiorze

$A=\{(g,y):g\left(x\right)=y\}.$

Dowolna permutacja $g$ wyznacza jednoznacznie element $y=g\left(x\right)$, tak więc $\left|A\right|=\left|G\right|.$ Pogrupowanie par $(g,y)\in A$ w zbiory $A_{y_1},\dots ,A_{y_m}$ tak, by

$A_{y_i}=\{(g,y_i):g\left(x\right)=y_i\}$

daje podział

$A=A_{y_1}\cup \dots \cup A_{y_m}.$

Zbiór $\{y_1,y_2,\dots ,y_m\}$ składa się z elementów, które można uzyskać jako $g\left(x\right)$ za pomocą jakiejkolwiek permutacji $g\in G$, a zatem jest to orbita elementu $x$:

$Gx=\{y_1,y_2,\dots ,y_m\}.$

Z kolei zaś $A_{y_i}$ jest zbiorem takich par $(g,y_i)$, że $g\left(x\right)=y_i$. Permutacja $g$ jednoznacznie wyznacza element $y_i=g\left(x\right)$, tak więc $A_{y_i}$ jest równoliczny z

$G(x\to y_i)=\{g\in G:g\left(x\right)=y_i\}.$

Tym samym Obserwacja Uzupelnic obs equation between orbits| daje, że $\left|A_{y_i}\right|=\left|G(x\to y_i)\right|=\left|G_x\right|$ dla dowolnego $i=1,2,\dots ,m$. W konsekwencji $\left|A\right|=\left|Gx\right|\cdot \left|G_x\right|$.

Wniosek

W G-zbiorze $(G,X)$ wszystkie orbity mają tę samą liczność, tzn.

$\left|Gx\right|=\left|Gy\right|\text{<mrow data-mjx-texclass="ORD">dladowolnych</mrow>}x,y\in X.$

Zbiór punktów stałych permutacji $g\in G$ to

Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf Fix}\left( g \right)=\left\lbrace x\in X:\ g\!\left( x \right)=x \right\rbrace. }

Twierdzenie

Dla G-zbioru $(G,X)$ oraz funkcji $f$ stałej na każdej orbicie $Gx$ zachodzi

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \sum_{x\in D}f\!\left( x \right)=\frac{1}{\left\vert G \right\vert}\sum_{g\in G} \sum_{x\in {\sf Fix}\left( g \right)} f\!\left( x \right), }

gdzie $D\subseteq X$ jest zbiorem reprezentantów orbit, tzn. $|D\cap Gx|=1$ dla dowolnego $x\in X$.

Dowód

Policzymy, na dwa różne sposoby, sumę

$\sum _{(g,x)\in B}f\left(x\right)$

gdzie $B=\{(g,x):g\left(x\right)=x\}$. Pogrupowanie par $(g,x)\in B$ w zbiory $B_{x_1},B_{x_2},\dots ,B_{x_n}$, zdefiniowane przez

$B_{x_i}=\{(g,x_i):g\left(x_i\right)=x_i\},$

daje podział

$B=B_{x_1}\cup B_{x_2}\cup \dots \cup B_{x_n}.$

Oczywiście $id\left(x\right)=x$, więc $(id,x)\in B_x$, czyli zbiór użytych w tym podziale indeksów $\{x_1,x_2,\dots ,x_n\}$ wyczerpuje całe $X$. Ponadto, z samej definicji $B_x$, otrzymujemy $\left|B_x\right|=\left|G_x\right|$. A zatem

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \sum_{\left( g,x \right)\in B}f\!\left( x \right) =\sum_{x\in X}\sum_{\left( g,x \right)\in B_x}f\!\left( x \right) =\sum_{x\in X}\left\vert G_x \right\vertf\!\left( x \right)=\left\vert G_{x_0} \right\vert\sum_{x\in X}f\!\left( x \right), }

gdzie $x_0$ jest dowolnie wybranym elementem zbioru $X$. Niech teraz $D=\{x_{i_0},x_{i_1},\dots ,x_{i_k}\}$ będzie zbiorem reprezentantów rodziny orbit, tzn. $G{x}_{i_j}$ są parami rozłączne i $X=G{x}_{i_0}\cup G{x}_{i_1}\cup \dots \cup G{x}_{i_k}$. Ponieważ funkcja $f$ jest stała na orbitach, to

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vert G_{x_0} \right\vert\sum_{x\in X}f\!\left( x \right) =\left\vert G_{x_0} \right\vert\sum_{x_{i_j}\in D}\sum_{y\in Gx_{i_j}}f\!\left( y \right) =\left\vert G_{x_0} \right\vert\sum_{x_{i_j}\in D}\left\vert Gx_{i_j} \right\vertf\!\left( x_{i_j} \right). }

Równoliczność orbit uzyskana we Wniosku [[##con Gx = Gy|Uzupelnic con Gx = Gy|]] wraz z Twierdzeniem [[##th Gx*Gx=G|Uzupelnic th Gx*Gx=G|]] daje więc

$\sum _{(g,x)\in B}f\left(x\right)=\left|G_{x_0}\right|\cdot \left|G{x}_0\right|\sum _{x\in D}f\left(x\right)=\left|G\right|\sum _{x\in D}f\left(x\right).$

Z drugiej strony, pogrupowanie par $(g,x)\in B$ w zbiory $B^{g_1},B^{g_2},\dots ,B^{g_m}$ zadane przez

$B^{g_i}=\{(g_i,x):g_i\left(x\right)=x\}$

daje podział

$B=B^{g_1}\cup B^{g_2}\cup \dots \cup B^{g_m}.$

Każdy zbiór postaci $B^{g_i}$ jest bijektywny ze zbiorem punktów stałych permutacji $g_i$

Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf Fix}\left( g_i \right)=\left\lbrace x\in X:\ \left( g_i,x \right)\in B^{g_i} \right\rbrace. }

A zatem

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \sum_{\left( g,x \right)\in B}f\!\left( x \right)=\sum_{g\in G} \sum_{x\in {\sf Fix}\left( g \right)} f\!\left( x \right), }

co daje ostatecznie

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vert G \right\vert\sum_{x\in D}f\!\left( x \right)=\sum_{g\in G} \sum_{x\in {\sf Fix}\left( g \right)} f\!\left( x \right). }

Wniosek

Liczba orbit w G-zbiorze $(G,X)$ wynosi

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \frac{1}{\left\vert G \right\vert}\sum_{g\in G}\left\vert {\sf Fix}\left( g \right) \right\vert. }

Permutacje na zbiorze kolorowań. Niech $(G,X)$ będzie G-zbiorem, a $A$ zbiorem kolorowań zbioru $X$. Każda permutacja $g\in G$ wyznacza permutację $\hat{g}:A⟶A$ kolorowań ze zbioru $A$ poprzez

$\left(\hat{g}\left(\omega \right)\right)\left(x\right)=\omega \left(g\left(x\right)\right)\text{<mrow data-mjx-texclass="ORD">dladowolnych</mrow>}\omega \in A\text{i}x\in X.$

Obserwacja

Niech $(G,X)$ będzie G-zbiorem, a $A$ zbiorem kolorowań zbioru $X$. Dla $\hat{G}=\{\hat{g}:g\in G\}$ zachodzi:

• Para $(\hat{G},\circ )$ tworzy grupę,

gdzie $\circ$ jest składaniem permutacji.

• Funkcja $\hat{\cdot }:G⟶\hat{G}$

jest izomorfizmem grup $(G,\circ )$ oraz $(\hat{G},\circ )$.

• $\left|G\right|=\left|\hat{G}\right|$.

• $(\hat{G},A)$ jest G-zbiorem.

Izomorficzne kolorowania. Kolorowania ${\omega }_0$ i ${\omega }_1$ zbioru $X$ są izomorficzne względem działania grupy $G$ na zbiorze $X$, gdy istnieje permutacja $g\in G$ taka, że $\hat{g}\left({\omega }_0\right)={\omega }_1$, czyli

${\omega }_0\left(g\left(x\right)\right)={\omega }_1\left(x\right)\text{<mrow data-mjx-texclass="ORD">dladowolnego</mrow>}x\in X.$

Przykład

Kolorowania z rysunku Uzupelnic pict pieciokat| są izomorficzne względem działania grupy ${\mathbf{𝐃}}_5$ wszystkich zmian ustawień $5$-elementowego naszyjnika.

Indeks permutacji $g:X⟶X$ to funkcja $n$ zmiennych

${\zeta }_g(x_1,\dots ,x_n)=x_1^{{\alpha }_1}\cdot x_2^{{\alpha }_2}\cdot \dots \cdot x_n^{{\alpha }_n},$

gdzie

• $n$ to liczność zbioru $X$,

• ${\alpha }_i$ to liczba $i$-elementowych cykli permutacji $g$,

dla $i=1,2,\dots ,n$.

Indeks grupy $G$ to funkcja $n$ zmiennych

${\zeta }_G(x_1,\dots ,x_n)=\frac{1}{\left|G\right|}\sum _{g\in G}{\zeta }_g(x_1,\dots ,x_n).$

Przykład

Niech $(G_t,\circ )$ będzie grupą wszystkich obrotów czworościanu foremnego (przedstawionego na rysunku Uzupelnic pict tetrahedron|) w $3$-wymiarowej przestrzeni.

[!h]

{poly_tetrahedron} {Czworościan $v_0{v}_1{v}_2{v}_3$. [Rysunek z pliku: polytetrahedron.eps]}

Obroty czworościanu mają więc następujące indeksy ${\zeta }_g(x_1,x_2,\dots ,x_8)$, w zależności od rozkładu na cykle:

• $x_1^4$ -- jedyny taki obrót z jednoelementowymi cyklami to oczywiście

$id=\left(0\right)\left(1\right)\left(2\right)\left(3\right)$.

• $x_1{x}_3$ -- obroty o $120^{\circ }$ względem prostej przechodzącej

przez jeden z wierzchołków i środek przeciwległej ściany. W grupie $G_t$ jest ich $8$. Przykładem permutacji o indeksie $x_1{x}_3$ jest $\left(0\right)\left(123\right)$, która odpowiada przekształceniu przedstawionym na rysunku Uzupelnic pict tetrahedron 2|.

[!h]

{poly_tetrahedron_2} {Obrót o $120^{\circ }$ czworościanu $v_0{v}_1{v}_2{v}_3$ względem prostej przechodzącej przez wierzchołek $v_0$ oraz przez środek ściany $v_1{v}_2{v}_3$. [Rysunek z pliku: polytetrahedron2.eps]}

• $x_2^2$ -- obroty o $180^{\circ }$ względem osi przechodzącej

przez środki przeciwległych krawędzi. W sumie są $3$ takie obroty. Permutacją o indeksie $x_2^2$ jest na przykład $\left(03\right)\left(12\right)$ i odpowiada ona przekształceniu przedstawionym na rysunku Uzupelnic pict tetrahedron 3|.

[!h]

{poly_tetrahedron_3} {Obrót o $180^{\circ }$ czworościanu $v_0{v}_1{v}_2{v}_3$ względem prostej przechodzącej przez środki krawędzi $v_1{v}_2$ oraz $v_0{v}_3$. [Rysunek z pliku: polytetrahedron3.eps]}

Indeks całej grupy obrotów czworościanu to zatem:

${\zeta }_{G_t}(x_1,x_2,x_3,x_4)=\frac{1}{12}(x_1^4+8x_1{x}_3+3x_2^2).$

Twierdzenie

Liczba nieizomorficznych kolorowań zbioru $X$ za pomocą $k$ barw wynosi

${\zeta }_G(k,k,\dots ,k),$

gdzie $G$ jest grupą możliwych permutacji elementów $X$.

Dowód

Niech $A$ będzie zbiorem wszystkich kolorowań $k$ barwami zbioru $X$. Szukana liczba nieizomorficznych kolorowań jest równa liczbie orbit G-zbioru $(\hat{G},A)$ i, na mocy Wniosku Uzupelnic con liczba orbit| oraz Obserwacji Uzupelnic obs G - G daszek|, wynosi:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \frac{1}{\left\vert \widehat{G} \right\vert}\sum_{\widehat{g}\in\widehat{G}}\left\vert {\sf Fix}\left( \widehat{g} \right) \right\vert =\frac{1}{\left\vert G \right\vert}\sum_{g\in G}\left\vert {\sf Fix}\left( {g} \right) \right\vert. }

Pozostaje więc policzyć liczbę punktów stałych każdej z permutacji $\hat{g}$ . Jeśli $\omega$ jest punktem stałym permutacji $\hat{g}$, a $(i_1,i_2,\dots ,i_l)$ jest cyklem tej permutacji, to

$\omega \left(i_{j+1}\right)=\omega \left(g\left(i_j\right)\right)=\left(\hat{g}\left(\omega \right)\right)\left(i_j\right)=\omega \left(i_j\right).$

A zatem wszystkie elementy $i_j$ tego cyklu są pokolorowane na ten sam kolor. Niech teraz permutacja $g$ rozkłada się na $m$ cykli. Ponieważ elementy każdego cyklu muszą być jednobarwne, a wszystkich możliwych do wykorzystania barw jest $k$, to liczba możliwych kolorowań elementów $X$ wynosi Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vert {\sf Fix}\left( g \right) \right\vert=k^m} . Z drugiej strony

${\zeta }_g(k,k,\dots ,k)=k^{{\alpha }_1}\cdot k^{{\alpha }_2}\cdot \dots \cdot k^{{\alpha }_s},$

gdzie ${\alpha }_i$ jest liczbą cykli $i$ elementowych. Ale oczywiście ${\alpha }_1+{\alpha }_2+\dots +{\alpha }_s=m$, skąd Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vert {\sf Fix}\left( g \right) \right\vert=\zeta_{g}\left( k,k,\ldots,k \right)} . Liczba nieizomorficznych kolorowań jest więc równa

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \frac{1}{\left\vert G \right\vert}\sum_{g\in G}\left\vert {\sf Fix}\left( g \right) \right\vert =\frac{1}{\left\vert G \right\vert}\sum_{g\in G} \zeta_{g}\left( k,k,\ldots,k \right) =\zeta_{G}\left( k,k,\ldots,k \right). }

Przykład

Niech $(G_t,\circ )$ będzie grupą wszystkich obrotów czworościanu foremnego (przedstawionego na rysunku Uzupelnic pict tetrahedron|) w $3$-wymiarowej przestrzeni. Wiemy już, że indeks grupy $G_t$ wynosi

${\zeta }_{G_t}(x_1,x_2,x_3,x_4)=\frac{1}{12}(x_1^4+8x_1{x}_3+3x_2^2).$

Aby zliczyć wszystkie, nieizomorficzne względem obrotów, kolorowania wierzchołków czworościanu na $2$ kolory wystarczy, wobec Twierdzenia Uzupelnic th g(k,k,...,k)|, policzyć wartość

${\zeta }_{G_t}(2,2,2,2)=5.$

Faktycznie. Jedynymi kolorowaniami nieizomorficznymi względem obrotów są te, przedstawione na rysunku Uzupelnic pict tetrahedron 4|.

[!h]

{poly_tetrahedron_4} {Nieizomorficzne kolorowania wierzchołków czworościanu foremnego. [Rysunek z pliku: polytetrahedron4.eps]}

Wskaźnik kolorowania $\omega :X⟶K$, dla zbioru kolorów $K=\{1,2,\dots ,k\}$ to

Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf ind}\left( \omega \right)=x_1^{n_1}\cdot x_2^{n_2}\cdot\ldots\cdot x_k^{n_k}, }

gdzie $n_i$ to liczba elementów ze zbioru $X$ pokolorowanych przez $\omega$ na kolor $i$.
Ponadto dla zbioru kolorowań $A$ definiuje się funkcję tworzącą postaci

Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf U}_{A}\left( x_1,x_2,\ldots,x_k \right)=\sum_{\omega\in A}{\sf ind}\left( \omega \right) =\sum_{\omega\in A}x_1^{n_1\left( \omega \right)}\cdot x_2^{n_2\left( \omega \right)}\cdot\ldots\cdot x_k^{n_k\left( \omega \right)}. }

Twierdzenie

Dla podziału zbioru $X=Y_1\cup Y_2\cup \dots \cup Y_l$ mamy

Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf U}_{D}\left( x_1,x_2,\ldots,x_k \right)=\prod_{i=1}^l\left( x_1^{\left\vert Y_i \right\vert} +x_2^{\left\vert Y_i \right\vert} +\ldots+ x_k^{\left\vert Y_i \right\vert} \right), }

gdzie $D$ jest zbiorem kolorowań stałych na zbiorach $Y_i$.

Dowód

Niech $\left|Y_i\right|=m_i$. Iloczyn

$\prod _{i=1}^l(x_1^{m_i}+x_2^{m_i}+\dots +x_k^{m_i})$

jest sumą jednomianów postaci $\beta x_1^{{\alpha }_1}{x}_2^{{\alpha }_2}\dots x_k^{{\alpha }_k}$. Aby przeanalizować te jednomiany zauważmy, że mnożąc po jednym składniku $x_j^{m_i}$ z każdego czynnika iloczynu, otrzymamy jednomian postaci $x_1^{{\alpha }_1}{x}_2^{{\alpha }_2}\dots x_k^{{\alpha }_k}$. Wartość $\beta$ jest więc równa wszystkim możliwym iloczynom $x_{j_1}^{m_1}{x}_{j_2}^{m_2}\dots x_{j_l}^{m_l}$ dającym $x_1^{{\alpha }_1}{x}_2^{{\alpha }_2}\dots x_k^{{\alpha }_k}$. Porządkując składniki $x_{j_i}$ otrzymujemy, że $\beta$ jest liczbą wszystkich zestawów sum postaci

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned \alpha_1&=&m_{i_{1,1}}+\ldots+m_{i_{1,{s_1}}}\\ \alpha_2&=&m_{i_{2,1}}+m_{i_{2,2}}+\ldots+m_{i_{2,{s_2}}}\\ &\cdots&\\ \alpha_k&=&m_{i_{k,1}}+\ldots+m_{i_{k,{s_k}}}. \endaligned}

Każdy taki zestaw sum można utożsamić z kolorowaniem, które przyporządkowuje elementom z $Y_{i_{1,1}}\cup \dots \cup Y_{i_{1,s_1}}$ pierwszą barwę, elementom z $Y_{i_{2,1}}\cup Y_{i_{2,2}}\cup \dots \cup Y_{i_{2,s_2}}$ kolejną barwę, itd... Otrzymujemy w ten sposób, że $\beta$ jest liczbą kolorowań stałych na każdym ze zbiorów $Y_i$. Kolorowania te używają ${\alpha }_1$ razy pierwszej barwy, ${\alpha }_2$ razy drugiej barwy, itd..., czyli jednomian $\beta x_1^{{\alpha }_1}{x}_2^{{\alpha }_2}\dots x_k^{{\alpha }_k}$ jest składnikiem w sumie powstałej z iloczynu Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf U}_{D}\left( x_1,x_2,\ldots,x_k \right)} przez wymnożenie wszystkich czynników.

Twierdzenie G. Pólya 1935

Niech $\left|X\right|=n$ a $D$ będzie zbiorem wszystkich nieizomorficznych, ze względu na działanie grupy $G$ na zbiorze $X$, kolorowań zbioru $X$ za pomocą $k$ barw. Wtedy funkcja tworząca Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf U}_{D}} jest postaci

Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf U}_{D}\left( x_1,x_2,\ldots,x_k \right)=\zeta_{G}\left( \sigma_1,\sigma_2,\ldots,\sigma_n \right), }

gdzie

${\sigma }_i=x_1^i+x_2^i+\dots +x_k^i.$

Dowód

Zbiór $D$ jest zbiorem reprezentantów orbit G-zbioru $(\hat{G},A)$, gdzie $A$ jest zbiorem wszystkich możliwych kolorowań zbioru $X$. Podstawiając, w Twierdzeniu Uzupelnic th ilosc orbit|, za funkcję $f$ wskaźnik kolorowania Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf ind}} otrzymujemy

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \sum_{\omega\in D}{\sf ind}\left( \omega \right) =\frac{1}{\left\vert \widehat{G} \right\vert}\sum_{\widehat{g}\in \widehat{G}} \left( \sum_{\omega \in {\sf Fix}\left( \widehat{g} \right)} {\sf ind}\left( \omega \right) \right). }

Korzystając z definicji wskaźnika kolorowania dostajemy

Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf U}_{D}\left( x_1,x_2,\ldots,x_k \right) =\frac{1}{\left\vert \widehat{G} \right\vert}\sum_{\widehat{g}\in \widehat{G}} {\sf U}_{{\sf Fix}\left( \widehat{g} \right)}\left( x_1,x_2,\ldots,x_k \right). }

Zbiór Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf Fix}\left( \widehat{g} \right)} jest zbiorem kolorowań, przy których elementy z tego samego cyklu otrzymują tę samą barwę. A zatem, z Twierdzenia [[##th U=()*()*()|Uzupelnic th U=()*()*()|]] wynika, że

Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf U}_{{\sf Fix}\left( \widehat{g} \right)}\left( x_1,x_2,\ldots,x_k \right) =\prod_{i=1}^l\left( x_1^{m_i} +x_2^{m_i} +\ldots+ x_k^{m_i} \right)=\prod_{i=1}^l\sigma_{m_i}, }

gdzie $m_i$ jest rozmiarem $i$-tego cyklu. Niech ${\alpha }_i$ będzie liczbą cykli w $g$ o długości $i$. Otrzymujemy więc

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned {\sf U}_{{\sf Fix}\left( \widehat{g} \right)}\left( x_1,x_2,\ldots,x_k \right)&=&\sigma_1^{\alpha_1}\cdot\sigma_2^{\alpha_2}\cdot\ldots\cdot\sigma_n^{\alpha_n}\\ &=&\zeta_{g}\left( \sigma_1,\sigma_2,\ldots,\sigma_n \right). \endaligned}

Obserwacja Uzupelnic obs G - G daszek| daje więc teraz

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned {\sf U}_{D}\left( x_1,x_2,\ldots,x_k \right) &=&\frac{1}{\left\vert \widehat{G} \right\vert}\sum_{\widehat{g}\in \widehat{G}} {\sf U}_{{\sf Fix}\left( \widehat{g} \right)}\left( x_1,x_2,\ldots,x_k \right)\\ &=&\frac{1}{\left\vert G \right\vert}\sum_{g\in G} \zeta_{g}\left( \sigma_1,\sigma_2,\ldots,\sigma_n \right)\\ &=&\zeta_{G}\left( \sigma_1,\sigma_2,\ldots,\sigma_n \right). \endaligned}

Przykład

Użyjemy opisanych twierdzeń do wyznaczenia liczby wszystkich nieizomorficznych pokolorowań wierzchołków kwadratu na dwa kolory. Rozważmy więc wszystkie osiem symetrii kwadratu, jak przedstawiono na rysunku Uzupelnic pict square 2|.

[!h]

{poly_square_2} {Przekształcenia geometryczne kwadratu. [Rysunek z pliku: polysquare2.eps]}

Grupa permutacji $G_{\mathrm{♢}}$ wyznaczona przez te symetrie ma $8$ następujących elementów:

$\begin{array}{lll}id=\left(0\right)\left(1\right)\left(2\right)\left(3\right)& & g_4=\left(0\right)\left(3\right)\left(12\right)\\ g_1=\left(0123\right)& & g_5=\left(1\right)\left(2\right)\left(03\right)\\ g_2=\left(02\right)\left(13\right)& & g_6=\left(02\right)\left(13\right)\\ g_3=\left(0321\right)& & g_7=\left(01\right)\left(23\right)\end{array}$

Z podanego rozkładu na cykle dostajemy, że indeks grupy $G_{\mathrm{♢}}$ to

${\zeta }_{G_{\mathrm{♢}}}(x_1,x_2,x_3,x_4)=\frac{1}{8}(x_1^4+2x_1^2{x}_2+3x_2^2+2x_4).$

Aby znaleźć liczbę nieizomorficznych kolorowań takich, że $i$ wierzchołków jest pokolorowanych na biało $◻$, a pozostałe $4-i$ na czarno $◼$, wystarczy wyliczyć współczynnik przy ${◻}^i{◼}^{4-i}$ w funkcji tworzącej postaci

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned {\sf U}_{D}\left( \square,\blacksquare \right)&=&\zeta_{G_{\diamondsuit}}\left( \square+\blacksquare,\ \square^2+\blacksquare^2,\ \square^3+\blacksquare^3,\ \square^4+\blacksquare^4 \right)\\ &=&\square^4+\square^3\blacksquare+2\square^2\blacksquare^2+\square\blacksquare^3+\blacksquare^4. \endaligned}

Rysunek Uzupelnic pict square 3| przedstawia wszystkie możliwe nieizomorficzne kolorowania.

[!h]

{poly_square_3} {Nieizomorficzne kolorowania wierzchołków kwadratu. [Rysunek z pliku: polysquare3.eps]}