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

Kolorowanie zbioru $X$ to funkcja

$\omega :X\longrightarrow K$,

gdzie $K$ jest zbiorem kolorów.

Poly pieciokat.swf

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_{\left(i-1\ mod\ 5\right)}\right)$ jest nieodróżnialne od kolorowania $\omega _{0}\!\left(k_{i}\right)$. Przekształcenie indeksów $i-1\ mod\ 5$ jest równoważne z obrotem o $72^{\circ }$.

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 {D} }_{5}$ symetrii pięciokąta. W wykładzie tym poznamy metody zliczania tych kolorowań, które są odróżnialne.

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

• $X$ jest zbiorem skończonym,

• ${\mathbf {G} }=\left(G,\circ \right)$ jest grupą permutacji zbioru $X$, tzn. $G$ jest zamkniętym na składanie

zbiorem permutacji zbioru $X$.

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

Przekształcenia odpowiadające permutacjom $id,g_{1},g_{2},g_{3}$

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.

Każde przedstawione przekształcenie geometryczne wyznacza jednoznacznie permutację zbioru indeksów wierzchołków kwadratu $X_{\square }=\left\lbrace 0,1,2,3\right\rbrace$. Tak więc zbiór permutacji odpowiadających przekształceniom to $G_{\square }=\left\lbrace id,g_{1},g_{2},g_{3}\right\rbrace$. 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 $\left(G_{\square },\circ \right)$ tworzy grupę, więc $\left(G_{\square },X_{\square }\right)$ jest przykładem G-zbioru, który jest opisany przez poniższe tabelki:

${\begin{array}{|c||c|c|c|c|}\hline j&1&2&3&4\\\hline \hline id(j)&0&1&2&3\\\hline g_{1}(j)&0&2&1&3\\\hline g_{2}(j)&3&1&2&0\\\hline g_{3}(j)&3&2&1&0\\\hline \end{array}}\quad \quad \quad \quad \quad {\begin{array}{|c||c|c|c|c|}\hline g_{i}\circ g_{j}&id&g_{1}&g_{2}&g_{3}\\\hline \hline id&id&g_{1}&g_{2}&g_{3}\\\hline g_{1}&g_{1}&id&g_{3}&g_{2}\\\hline g_{2}&g_{2}&g_{3}&id&g_{1}\\\hline g_{3}&g_{3}&g_{2}&g_{1}&id\\\hline \end{array}}$

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

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

$Gx=\left\lbrace g\!\left(x\right)\in X:g\in G\right\rbrace$

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

$G_{x}=\left\lbrace g\in G:\ g\!\left(x\right)=x\right\rbrace$

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

$G\left(x\rightarrow y\right)=\left\lbrace g\in G:\ g\!\left(x\right)=y\right\rbrace$

Przykład

Dla grupy $G_{\square }$ permutacji kwadratu z rysunku, orbita oraz stabilizator elementu $0$ mają postać

$G_{\square }0=\left\lbrace 0,3\right\rbrace \quad \quad \quad \quad G_{\square ,0}=\left\lbrace id,g_{1}\right\rbrace$

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

Jako ćwiczenie 3 pozostawiamy dowód następującej obserwacji.

Obserwacja 5.1

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

$\left\vert G_{x}\right\vert =\left\vert G\left(x\rightarrow y\right)\right\vert =\left\vert G\left(y\rightarrow x\right)\right\vert =\left\vert G_{y}\right\vert$

Twierdzenie 5.2

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

$\left\vert Gx\right\vert \cdot \left\vert G_{x}\right\vert =\left\vert G\right\vert$

Dowód

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

$A=\left\lbrace \left(g,y\right):\ g\!\left(x\right)=y\right\rbrace$

Dowolna permutacja $g$ wyznacza jednoznacznie element $y=g\!\left(x\right)$, tak więc $\left\vert A\right\vert =\left\vert G\right\vert$ Pogrupowanie par $\left(g,y\right)\in A$ w zbiory $A_{y_{1}},\ldots ,A_{y_{m}}$ tak, by

$A_{y_{i}}=\left\lbrace \left(g,y_{i}\right):\ g\!\left(x\right)=y_{i}\right\rbrace$

daje podział

$A=A_{y_{1}}\cup \ldots \cup A_{y_{m}}$

Zbiór $\left\lbrace y_{1},y_{2},\ldots ,y_{m}\right\rbrace$ 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=\left\lbrace y_{1},y_{2},\ldots ,y_{m}\right\rbrace$

Z kolei zaś $A_{y_{i}}$ jest zbiorem takich par $\left(g,y_{i}\right)$, ż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\!\left(x\rightarrow y_{i}\right)=\left\lbrace g\in G:\ g\!\left(x\right)=y_{i}\right\rbrace$

Tym samym Obserwacja 5.1 daje, że $\left\vert A_{y_{i}}\right\vert =\left\vert G\!\left(x\rightarrow y_{i}\right)\right\vert =\left\vert G_{x}\right\vert$ dla dowolnego $i=1,2,\ldots ,m$. W konsekwencji $\left\vert A\right\vert =\left\vert Gx\right\vert \cdot \left\vert G_{x}\right\vert$.

Wniosek 5.3

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

$\left\vert Gx\right\vert =\left\vert Gy\right\vert \quad {\text{dla dowolnych}}\ x,y\in X$

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

${\mathsf {Fix}}\left(g\right)=\left\lbrace x\in X:g\!\left(x\right)=x\right\rbrace$

Twierdzenie 5.4

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

$\sum _{x\in D}f\!\left(x\right)={\frac {1}{\left\vert G\right\vert }}\sum _{g\in G}\sum _{x\in {\mathsf {Fix}}\left(g\right)}f\!\left(x\right)$,

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

Dowód

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

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

gdzie $B=\left\lbrace \left(g,x\right):g\!\left(x\right)=x\right\rbrace$. Pogrupowanie par $\left(g,x\right)\in B$ w zbiory $B_{x_{1}},B_{x_{2}},\ldots ,B_{x_{n}}$, zdefiniowane przez

$B_{x_{i}}=\left\lbrace \left(g,x_{i}\right):g\!\left(x_{i}\right)=x_{i}\right\rbrace$,

daje podział

$B=B_{x_{1}}\cup B_{x_{2}}\cup \ldots \cup B_{x_{n}}$

Oczywiście $id\left(x\right)=x$, więc $\left(id,x\right)\in B_{x}$, czyli zbiór użytych w tym podziale indeksów $\left\lbrace x_{1},x_{2},\ldots ,x_{n}\right\rbrace$ wyczerpuje całe $X$. Ponadto, z samej definicji $B_{x}$, otrzymujemy $\left\vert B_{x}\right\vert =\left\vert G_{x}\right\vert$. A zatem

$\sum _{\left(g,x\right)\in B}f\!\left(x\right)=\sum _{x\in X}\sum _{(g,x)\in B_{x}}f\!\left(x\right)=\sum _{x\in X}\left\vert G_{x}\right\vert f\!\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=\left\lbrace x_{i_{0}},x_{i_{1}},\ldots ,x_{i_{k}}\right\rbrace$ będzie zbiorem reprezentantów rodziny orbit, tzn. $Gx_{i_{j}}$ są parami rozłączne i $X=Gx_{i_{0}}\cup Gx_{i_{1}}\cup \ldots \cup Gx_{i_{k}}$. Ponieważ funkcja $f$ jest stała na orbitach, to

$\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\vert f\!\left(x_{i_{j}}\right)$

Równoliczność orbit uzyskana we Wniosku 5.3 wraz z Twierdzeniem 5.2 daje więc

$\sum _{\left(g,x\right)\in B}f\!\left(x\right)=\left\vert G_{x_{0}}\right\vert \cdot \left\vert Gx_{0}\right\vert \sum _{x\in D}f\!\left(x\right)=\left\vert G\right\vert \sum _{x\in D}f\!\left(x\right)$

Z drugiej strony, pogrupowanie par $\left(g,x\right)\in B$ w zbiory $B^{g_{1}},B^{g_{2}},\ldots ,B^{g_{m}}$ zadane przez

$B^{g_{i}}=\left\lbrace \left(g_{i},x\right):g_{i}\!\left(x\right)=x\right\rbrace$

daje podział

$B=B^{g_{1}}\cup B^{g_{2}}\cup \ldots \cup B^{g_{m}}$

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

${\mathsf {Fix}}\left(g_{i}\right)=\left\lbrace x\in X:\left(g_{i},x\right)\in B^{g_{i}}\right\rbrace$

A zatem

$\sum _{\left(g,x\right)\in B}f\!\left(x\right)=\sum _{g\in G}\sum _{x\in {\mathsf {Fix}}\left(g\right)}f\!\left(x\right)$,

co daje ostatecznie

$\left\vert G\right\vert \sum _{x\in D}f\!\left(x\right)=\sum _{g\in G}\sum _{x\in {\mathsf {Fix}}\left(g\right)}f\!\left(x\right)$

Wniosek 5.5

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

${\frac {1}{\left\vert G\right\vert }}\sum _{g\in G}\left\vert {\mathsf {Fix}}\left(g\right)\right\vert$

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

$\left({\widehat {g}}\!\left(\omega \right)\right)\!\left(x\right)=\omega \!\left(g\!\left(x\right)\right)\quad {\text{dla dowolnych}}\ \omega \in A\ {\text{i}}\ x\in X$

Obserwacja 5.6

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

• Para $\left({\widehat {G}},\circ \right)$ tworzy grupę, gdzie $\circ$ jest składaniem permutacji.

• Funkcja ${\widehat {\cdot }}:G\longrightarrow {\widehat {G}}$ jest izomorfizmem grup $\left(G,\circ \right)$ oraz $\left({\widehat {G}},\circ \right)$.

• $\left\vert G\right\vert =\left\vert {\widehat {G}}\right\vert$.

• $\left({\widehat {G}},A\right)$ 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 ${\widehat {g}}\!\left(\omega _{0}\right)=\omega _{1}$, czyli

$\omega _{0}\!\left(g\!\left(x\right)\right)=\omega _{1}\!\left(x\right)\quad {\text{dla dowolnego}}\ x\in X$

Przykład

Kolorowania z rysunku są izomorficzne względem działania grupy ${\mathbf {D} }_{5}$ wszystkich zmian ustawień $5$-elementowego naszyjnika.

Indeks permutacji $g:X\longrightarrow X$ to funkcja $n$ zmiennych

$\zeta _{g}\left(x_{1},\ldots ,x_{n}\right)=x_{1}^{\alpha _{1}}\cdot x_{2}^{\alpha _{2}}\cdot \ldots \cdot x_{n}^{\alpha _{n}}$,

gdzie

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

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

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

Indeks grupy $G$ to funkcja $n$ zmiennych

$\zeta _{G}\left(x_{1},\ldots ,x_{n}\right)={\frac {1}{\left\vert G\right\vert }}\sum _{g\in G}\zeta _{g}\left(x_{1},\ldots ,x_{n}\right)$

Plik:Poly tetrahedron.svg

Czworościan $v_{0}v_{1}v_{2}v_{3}$

Plik:Poly tetrahedron 2.svg

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

Plik:Poly tetrahedron 3.svg

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

Przykład

Niech $\left(G_{t},\circ \right)$ będzie grupą wszystkich obrotów czworościanu foremnego (przedstawionego na rysunku) w $3$-wymiarowej przestrzeni.

Obroty czworościanu mają więc następujące indeksy $\zeta _{g}\left(x_{1},x_{2},\ldots ,x_{8}\right)$, 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.

• $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.

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

$\zeta _{G_{t}}\left(x_{1},x_{2},x_{3},x_{4}\right)={\frac {1}{12}}\left(x_{1}^{4}+8x_{1}x_{3}+3x_{2}^{2}\right)$

Twierdzenie 5.7

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

$\zeta _{G}\left(k,k,\ldots ,k\right)$,

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 $\left({\widehat {G}},A\right)$ i, na mocy Wniosku 5.5 oraz Obserwacji 5.6, wynosi:

${\frac {1}{\left\vert {\widehat {G}}\right\vert }}\sum _{{\widehat {g}}\in {\widehat {G}}}\left\vert {\mathsf {Fix}}\left({\widehat {g}}\right)\right\vert ={\frac {1}{\left\vert G\right\vert }}\sum _{g\in G}\left\vert {\mathsf {Fix}}\left({g}\right)\right\vert$

Pozostaje więc policzyć liczbę punktów stałych każdej z permutacji ${\widehat {g}}$ . Jeśli $\omega$ jest punktem stałym permutacji ${\widehat {g}}$, a $\left(i_{1},i_{2},\ldots ,i_{l}\right)$ jest cyklem tej permutacji, to

$\omega \!\left(i_{j+1}\right)=\omega \!\left(g\!\left(i_{j}\right)\right)=\left({\widehat {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 $\left\vert {\mathsf {Fix}}\left(g\right)\right\vert =k^{m}$. Z drugiej strony

$\zeta _{g}\left(k,k,\ldots ,k\right)=k^{\alpha _{1}}\cdot k^{\alpha _{2}}\cdot \ldots \cdot k^{\alpha _{s}}$,

gdzie $\alpha _{i}$ jest liczbą cykli $i$ elementowych. Ale oczywiście $\alpha _{1}+\alpha _{2}+\ldots +\alpha _{s}=m$, skąd $\left\vert {\mathsf {Fix}}\left(g\right)\right\vert =\zeta _{g}\left(k,k,\ldots ,k\right)$. Liczba nieizomorficznych kolorowań jest więc równa

${\frac {1}{\left\vert G\right\vert }}\sum _{g\in G}\left\vert {\mathsf {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)$

Plik:Poly tetrahedron 4.svg

Nieizomorficzne kolorowania wierzchołków czworościanu foremnego

Przykład

Niech $\left(G_{t},\circ \right)$ będzie grupą wszystkich obrotów czworościanu foremnego (przedstawionego na rysunku) w $3$-wymiarowej przestrzeni. Wiemy już, że indeks grupy $G_{t}$ wynosi

$\zeta _{G_{t}}\left(x_{1},x_{2},x_{3},x_{4}\right)={\frac {1}{12}}\left(x_{1}^{4}+8x_{1}x_{3}+3x_{2}^{2}\right)$

Aby zliczyć wszystkie, nieizomorficzne względem obrotów, kolorowania wierzchołków czworościanu na $2$ kolory wystarczy, wobec Twierdzenia 5.7, policzyć wartość

$\zeta _{G_{t}}\left(2,2,2,2\right)=5$

Faktycznie. Jedynymi kolorowaniami nieizomorficznymi względem obrotów są te, przedstawione na rysunku.

Wskaźnik kolorowania $\omega :X\longrightarrow K$, dla zbioru kolorów $K=\left\lbrace 1,2,\ldots ,k\right\rbrace$ to

${\mathsf {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

${\mathsf {U}}_{A}\left(x_{1},x_{2},\ldots ,x_{k}\right)=\sum _{\omega \in A}{\mathsf {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 5.8

Dla podziału zbioru $X=Y_{1}\cup Y_{2}\cup \ldots \cup Y_{l}$ mamy

${\mathsf {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\vert Y_{i}\right\vert =m_{i}$. Iloczyn

$\prod _{i=1}^{l}\left(x_{1}^{m_{i}}+x_{2}^{m_{i}}+\ldots +x_{k}^{m_{i}}\right)$

jest sumą jednomianów postaci $\beta x_{1}^{\alpha _{1}}x_{2}^{\alpha _{2}}\ldots 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}}\ldots 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}}\ldots x_{j_{l}}^{m_{l}}$ dającym $x_{1}^{\alpha _{1}}x_{2}^{\alpha _{2}}\ldots x_{k}^{\alpha _{k}}$. Porządkując składniki $x_{j_{i}}$ otrzymujemy, że $\beta$ jest liczbą wszystkich zestawów sum postaci

${\begin{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}}}}.\end{aligned}}$

Każdy taki zestaw sum można utożsamić z kolorowaniem, które przyporządkowuje elementom z $Y_{i_{1,1}}\cup \ldots \cup Y_{i_{1,{s_{1}}}}$ pierwszą barwę, elementom z $Y_{i_{2,1}}\cup Y_{i_{2,2}}\cup \ldots \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}}\ldots x_{k}^{\alpha _{k}}$ jest składnikiem w sumie powstałej z iloczynu ${\mathsf {U}}_{D}\left(x_{1},x_{2},\ldots ,x_{k}\right)$ przez wymnożenie wszystkich czynników.

Twierdzenie 5.9 [G. Pólya 1935]

Niech $\left\vert X\right\vert =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 ${\mathsf {U}}_{D}$ jest postaci

${\mathsf {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}+\ldots +x_{k}^{i}$

Dowód

Zbiór $D$ jest zbiorem reprezentantów orbit G-zbioru $\left({\widehat {G}},A\right)$, gdzie $A$ jest zbiorem wszystkich możliwych kolorowań zbioru $X$. Podstawiając, w Twierdzeniu 5.4, za funkcję $f$ wskaźnik kolorowania ${\mathsf {ind}}$ otrzymujemy

$\sum _{\omega \in D}{\mathsf {ind}}\left(\omega \right)={\frac {1}{\left\vert {\widehat {G}}\right\vert }}\sum _{{\widehat {g}}\in {\widehat {G}}}\left(\sum _{\omega \in {\mathsf {Fix}}\left({\widehat {g}}\right)}{\mathsf {ind}}\left(\omega \right)\right)$

Korzystając z definicji wskaźnika kolorowania dostajemy

${\mathsf {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}}}{\mathsf {U}}_{{\mathsf {Fix}}\left({\widehat {g}}\right)}\left(x_{1},x_{2},\ldots ,x_{k}\right)$

Zbiór ${\mathsf {Fix}}\left({\widehat {g}}\right)$ jest zbiorem kolorowań, przy których elementy z tego samego cyklu otrzymują tę samą barwę. A zatem, z Twierdzenia 5.8 wynika, że

${\mathsf {U}}_{{\mathsf {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

${\begin{aligned}{\mathsf {U}}_{{\mathsf {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).\end{aligned}}$

Obserwacja 5.6 daje więc teraz

${\begin{aligned}{\mathsf {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}}}{\mathsf {U}}_{{\mathsf {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).\end{aligned}}$

Plik:Poly square 2.mp4

Przekształcenia geometryczne kwadratu

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

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

${\begin{array}{lp{20mm}l}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_{\diamondsuit }$ to

$\zeta _{G_{\diamondsuit }}\left(x_{1},x_{2},x_{3},x_{4}\right)={\frac {1}{8}}\left(x_{1}^{4}+2x_{1}^{2}x_{2}+3x_{2}^{2}+2x_{4}\right)$

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

${\begin{aligned}{\mathsf {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}.\end{aligned}}$

Rysunek przedstawia wszystkie możliwe nieizomorficzne kolorowania.

Nieizomorficzne kolorowania wierzchołków kwadratu