Kolorowanie zbioru \( X \) to funkcja
\( \omega:X\longrightarrow 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}\!( k_i )=\omega_{0}\!( k_{( i-1\ mod\ 5 )} ) \) jest nieodróżnialne od kolorowania \( \omega_{0}\!( k_i ) \). 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 \( ( {\mathbf G},X ) \), gdzie
Czasem, dla G-zbioru \( ( {\mathbf G},X ) \) mówimy, ze grupa \( {\mathbf G} \) 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.
Każde przedstawione przekształcenie geometryczne wyznacza jednoznacznie permutację zbioru indeksów wierzchołków kwadratu \( X_□=\lbrace 0,1,2,3 \rbrace \). Tak więc zbiór permutacji odpowiadających przekształceniom to \( G_□=\lbrace id,g_1,g_2,g_3 \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 \( ( G_□, \circ ) \) tworzy grupę, więc \( ( G_□, X_□ ) \) 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}_□ \) 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\!( x ) \) dla pewnego \( g\in G \), tzn.
\( Gx=\lbrace g\!( x )\in X: g\in G \rbrace. \)
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=\lbrace g\in G:\ g\!( x )=x \rbrace. \)
Ponadto zbiór permutacji przeprowadzających \( x\in X \) w \( y\in X \) oznaczamy przez
\( G( x \to y )=\lbrace g\in G:\ g\!( x )=y \rbrace \)
Przykład
Dla grupy \( G_□ \) permutacji kwadratu z rysunku, orbita oraz stabilizator elementu \( 0 \) mają postać
\( G_□0=\lbrace 0,3 \rbrace \quad\quad\quad\quad G_{□, 0}=\lbrace id,g_1 \rbrace. \)
Mnożąc liczności obu tych zbiorów otrzymujemy liczbę elementów grupy \( G_□ \), czyli innymi słowy \( \vert G_□ 0 \vert\cdot\vert G_{□, 0} \vert=\vert G_□ \vert. \)
Przypadek? Nie sądzę.
Twierdzenie 5.2
Dla G-zbioru \( ( G,X ) \) oraz \( x \in X \) zachodzi
\( \vert Gx \vert\cdot\vert G_x \vert=\vert G \vert. \)
Dowód
Pokażemy, że istnieje wzajemnie jednoznaczna odpowiedniość między elementami orbity \( Gx \) a warstwami \( G \) względem stabilizatora \( G_x \). Teza twierdzenia wyniknie wtedy natychmiast z twierdzenia Lagrange'a.
Mamy \( g_1(x) = g_2(x) \Leftrightarrow g_1^{-1}g_2(x) = x \Leftrightarrow g_1^{-1}g_2(x)\in G_x \Leftrightarrow g_2\in g_1G_x.\)
Zbiór punktów stałych permutacji \( g\in G \) to
\( {\sf Fix}( g )=\lbrace x\in X:\ g\!( x )=x \rbrace. \)
Twierdzenie 5.4
Dla G-zbioru \( ( G,X ) \) oraz funkcji \( f \) stałej na każdej orbicie \( Gx \) zachodzi
\( \displaystyle \sum_{x\in D}f\!( x )=\frac{1}{\vert G \vert}\sum_{g\in G} \sum_{x\in {\sf Fix}( g )} f\!( x ), \)
gdzie \( D\subseteq X \) jest zbiorem reprezentantów orbit, tzn. \( \vert D \cap Gx \vert=1 \) dla dowolnego \( x\in X \).
Dowód
Policzymy, na dwa różne sposoby, sumę
\( \displaystyle \sum_{( g,x )\in B}f\!( x ) \)
gdzie \( B=\lbrace ( g,x ):g\!( x )=x \rbrace \). Zliczając najpierw po \(g\in G\), a potem po \(x\in {\sf Fix}( g )\), dostajemy sumę
\[\sum_{g\in G} \sum_{x\in {\sf Fix}( g )} f\!( x ), \]
natomiast zliczając najpierw po \(x\in X\), a potem po \(g\in G_x\), dostajemy sumę
\[\sum_{x\in X}\vert G_x \vert f\!( x ) = \vert G \vert\sum_{x\in X}\frac{f\!( x )}{\vert Gx \vert}.\]
Każdy element orbity \( Gx\) wnosi do sumy taką samą wartość \(\frac{f\!( x )}{\vert Gx \vert}\) (bo \(f\) jest stała na każdej orbicie), zatem cała orbita \( Gx\) wnosi \( f(x)\), czyli ostatecznie \( \sum_{g\in G} \sum_{x\in {\sf Fix}( g )} f\!( x ) = \vert G\vert \sum_{x\in D}f\!( x )\).
Wniosek 5.5
Liczba orbit w G-zbiorze \( ( G,X ) \) wynosi
\( \displaystyle \frac{1}{\vert G \vert}\sum_{g\in G}\vert {\sf Fix}( g ) \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ę \( \widehat{g}:A\longrightarrow A \) kolorowań ze zbioru \( A \) poprzez
\( ( \widehat{g}\!( \omega ) )\!( x ) =\omega\!( g\!( x ) )\quad\textrm{dla dowolnych}\ \omega\in A\ \textrm{i}\ x\in X. \)
Obserwacja 5.6
Niech \( ( G,X ) \) będzie G-zbiorem, a \( A \) zbiorem kolorowań zbioru \( X \). Dla \( \widehat{G} = \lbrace \widehat{g}: g \in G \rbrace \) zachodzi:
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}\!( \omega_{0} ) = \omega_{1} \), czyli
\( \displaystyle \omega_{0}\!( g\!( x ) )=\omega_{1}\!( x )\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}( x_1,\ldots,x_n ) =x_1^{\alpha_1}\cdot x_2^{\alpha_2}\cdot\ldots\cdot x_n^{\alpha_n}, \)
gdzie
dla \( i=1,2,\ldots,n \).
Indeks grupy \( G \) to funkcja \( n \) zmiennych
\( \displaystyle \zeta_{G}( x_1,\ldots,x_n )=\frac{1}{\vert G \vert}\sum_{g\in G}\zeta_{g}( x_1,\ldots,x_n ). \)
Przykład
Niech \( ( G_t,\circ ) \) 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}( x_1,x_2,\ldots,x_8 ) \), w zależności od rozkładu na cykle:
W sumie są \( 3 \) takie obroty. Permutacją o indeksie \( x_2^2 \) jest na przykład \( ( 03 )\!( 12 ) \) i odpowiada ona przekształceniu przedstawionym na rysunku.
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_1x_3+3x_2^2 ). \)
Twierdzenie 5.7
Liczba nieizomorficznych kolorowań zbioru \( X \) za pomocą \( k \) barw wynosi
\( \zeta_{G}( k,k,\ldots,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 \( ( \widehat{G},A ) \) i, na mocy Wniosku 5.5 oraz Obserwacji 5.6, wynosi:
\( \displaystyle \frac{1}{\vert \widehat{G} \vert}\sum_{\widehat{g}\in\widehat{G}}\vert {\sf Fix}( \widehat{g} ) \vert =\frac{1}{\vert G \vert}\sum_{g\in G}\vert {\sf Fix}( {g} ) \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 \( ( i_1,i_2,\ldots,i_l ) \) jest cyklem tej permutacji, to
\( \displaystyle \omega\!( i_{j+1} ) =\omega\!( g\!( i_j ) ) =( \widehat{g}\!( \omega ) )\!( i_j )=\omega\!( i_j ). \)
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 \( \vert {\sf Fix}( g ) \vert=k^m \). Z drugiej strony
\( \displaystyle \zeta_{g}( k,k,\ldots,k ) =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 \( \vert {\sf Fix}( g ) \vert=\zeta_{g}( k,k,\ldots,k ) \). Liczba nieizomorficznych kolorowań jest więc równa
\( \displaystyle \frac{1}{\vert G \vert}\sum_{g\in G}\vert {\sf Fix}( g ) \vert =\frac{1}{\vert G \vert}\sum_{g\in G} \zeta_{g}( k,k,\ldots,k ) =\zeta_{G}( k,k,\ldots,k ). \)
Przykład
Niech \( ( G_t,\circ ) \) 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}( x_1,x_2,x_3,x_4 )=\frac{1}{12}( x_1^4+8x_1x_3+3x_2^2 ). \)
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}( 2,2,2,2 )=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=\lbrace 1,2,\ldots,k \rbrace \) to
\( {\sf ind}( \omega )=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}( x_1,x_2,\ldots,x_k )=\sum_{\omega\in A}{\sf ind}( \omega ) =\sum_{\omega\in A}x_1^{n_1( \omega )}\cdot x_2^{n_2( \omega )}\cdot\ldots\cdot x_k^{n_k( \omega )}. \)
Twierdzenie 5.8
Dla podziału zbioru \( X=Y_1\cup Y_2\cup\ldots\cup Y_l \) mamy
\( \displaystyle {\sf U}_{D}( x_1,x_2,\ldots,x_k )=\prod_{i=1}^l( x_1^{\vert Y_i \vert} +x_2^{\vert Y_i \vert} +\ldots+ x_k^{\vert Y_i \vert} ), \)
gdzie \( D \) jest zbiorem kolorowań stałych na zbiorach \( Y_i \).
Dowód
Niech \( \vert Y_i \vert=m_i \). Iloczyn
\( \displaystyle \prod_{i=1}^l( x_1^{m_i} +x_2^{m_i} +\ldots+ x_k^{m_i} ) \)
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{align*} \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{align*} \)
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}( x_1,x_2,\ldots,x_k ) \) przez wymnożenie wszystkich czynników.
Twierdzenie 5.9 [G. Pólya 1935]
Niech \( \vert X \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}( x_1,x_2,\ldots,x_k )=\zeta_{G}( \sigma_1,\sigma_2,\ldots,\sigma_n ), \)
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 \( ( \widehat{G},A ) \), 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}( \omega ) =\frac{1}{\vert \widehat{G} \vert}\sum_{\widehat{g}\in \widehat{G}} ( \sum_{\omega \in {\sf Fix}( \widehat{g} )} {\sf ind}( \omega ) ). \)
Korzystając z definicji wskaźnika kolorowania dostajemy
\( \displaystyle {\sf U}_{D}( x_1,x_2,\ldots,x_k ) =\frac{1}{\vert \widehat{G} \vert}\sum_{\widehat{g}\in \widehat{G}} {\sf U}_{{\sf Fix}( \widehat{g} )}( x_1,x_2,\ldots,x_k ). \)
Zbiór \( {\sf Fix}( \widehat{g} ) \) 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}( \widehat{g} )}( x_1,x_2,\ldots,x_k ) =\prod_{i=1}^l( x_1^{m_i} +x_2^{m_i} +\ldots+ x_k^{m_i} )=\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{align*} {\sf U}_{{\sf Fix}( \widehat{g} )}( x_1,x_2,\ldots,x_k ) & =\sigma_1^{\alpha_1}\cdot\sigma_2^{\alpha_2}\cdot\ldots\cdot\sigma_n^{\alpha_n} \\ & =\zeta_{g}( \sigma_1,\sigma_2,\ldots,\sigma_n ). \end{align*} \)
Obserwacja 5.6 daje więc teraz
\( \begin{align*} {\sf U}_{D}( x_1,x_2,\ldots,x_k ) & =\frac{1}{\vert \widehat{G} \vert}\sum_{\widehat{g}\in \widehat{G}} {\sf U}_{{\sf Fix}( \widehat{g} )}( x_1,x_2,\ldots,x_k ) \\ & =\frac{1}{\vert G \vert}\sum_{g\in G} \zeta_{g}( \sigma_1,\sigma_2,\ldots,\sigma_n ) \\ & =\zeta_{G}( \sigma_1,\sigma_2,\ldots,\sigma_n ). \end{align*} \)
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\ =\ ( 0 )\!( 1 )\!( 2 )\!( 3 ) & & g_4\ =\ ( 0 )\!( 3 )\!( 12 ) \\ g_1\ =\ ( 0123 ) & & g_5\ =\ ( 1 )\!( 2 )\!( 03 ) \\ g_2\ =\ ( 02 )\!( 13 ) & & g_6\ =\ ( 02 )\!( 13 ) \\ g_3\ =\ ( 0321 ) & & g_7\ =\ ( 01 )\!( 23 ) \end{array} \)
Z podanego rozkładu na cykle dostajemy, że indeks grupy \( G_{\diamondsuit} \) to
\( \zeta_{G_{\diamondsuit}}( x_1,x_2,x_3,x_4 ) =\frac{1}{8}( x_1^4+2x_1^2x_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
\( \begin{align*} {\sf U}_{D}( □,■ ) & =\zeta_{G_{\diamondsuit}}( □+■,\ □^2+■^2,\ □^3+■^3,\ □^4+■^4 ) \\ & =□^4+□^3■+2□
^2■^2+□ ■^3+■^4. \end{align*} \)
Rysunek przedstawia wszystkie możliwe nieizomorficzne kolorowania.
Nieizomorficzne kolorowania wierzchołków kwadratu