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

From Studia Informatyczne

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.

image:End_of_proof.gif

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\textrm{dla dowolnych}\ x,y\in X.


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


{\sf 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


\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. \left\vert D \cap Gx \right\vert=1 dla dowolnego x\in X.

Dowód

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


\displaystyle \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ł


\displaystyle 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


\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=\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


\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 5.3 wraz z Twierdzeniem 5.2 daje więc


\displaystyle \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


\displaystyle B^{g_i}=\left\lbrace \left( g_i,x \right):g_i\!\left( x \right)=x \right\rbrace


daje podział


\displaystyle 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


\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


\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


\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).


image:End_of_proof.gif

Wniosek 5.5

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


\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 \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\textrm{dla dowolnych}\ \omega\in A\ \textrm{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


\displaystyle \omega_{0}\!\left( g\!\left( x \right) \right)=\omega_{1}\!\left( x \right)\quad\textrm{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


\displaystyle \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).



Czworościan v_0v_1v_2v_3



Obrót o 120^{\circ} czworościanu v_0v_1v_2v_3 względem prostej przechodzącej przez wierzchołek v_0 oraz przez środek ściany v_1v_2v_3



Obrót o 180^{\circ} czworościanu v_0v_1v_2v_3 względem prostej przechodzącej przez środki krawędzi v_1v_2 oraz v_0v_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_1x_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_1x_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_1x_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:


\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 \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


\displaystyle \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 {\sf Fix}\left( g \right) \right\vert=k^m. Z drugiej strony


\displaystyle \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 {\sf Fix}\left( g \right) \right\vert=\zeta_{g}\left( k,k,\ldots,k \right). Liczba nieizomorficznych kolorowań jest więc równa


\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).


image:End_of_proof.gif



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_1x_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


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


\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 5.8

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


\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\vert Y_i \right\vert=m_i. Iloczyn


\displaystyle \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


\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\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 {\sf U}_{D}\left( x_1,x_2,\ldots,x_k \right) przez wymnożenie wszystkich czynników.

image:End_of_proof.gif

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 {\sf U}_{D} jest postaci


{\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+\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 {\sf ind} otrzymujemy


\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


\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 {\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 5.8 wynika, że


\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


\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 5.6 daje więc teraz


\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


image:End_of_proof.gif



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^2x_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


\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 przedstawia wszystkie możliwe nieizomorficzne kolorowania.



Nieizomorficzne kolorowania wierzchołków kwadratu