Processing math: 10%

Zastosowania teorii grup w zliczaniu

Kolorowanie zbioru X to funkcja

ω:XK,

gdzie K jest zbiorem kolorów.

Przykład

Rozważmy kolorowania naszyjnika złożonego z pięciu identycznych koralików k0,k1,k2,k3,k4. Koraliki te mają takie same kształty i nie można ich rozróżnić. Możemy zatem zauważyć, że z jednego kolorowania ω0 da się utworzyć inne kolorowanie, nieodróżnialne od pierwszego, np. przez cykliczną zmianę numeracji koralików: ω1(ki)=ω0(k(i1 mod 5)) jest nieodróżnialne od kolorowania ω0(ki). Przekształcenie indeksów i1 mod 5 jest równoważne z obrotem o 72.

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

G-zbiór to para (G,X), gdzie

  • X jest zbiorem skończonym,
  • G=(G,) jest grupą permutacji zbioru X, tzn. G jest zamkniętym na składanie zbiorem permutacji zbioru X.

Czasem, dla G-zbioru (G,X) mówimy, ze grupa G działa na zbiorze X.

Przykład

Rozważmy kwadrat o wierzchołkach v0,v1,v2,v3 oraz 4 permutacje jego wierzchołków powstałe przez: odbicia względem przekątnych i obrót o 180, 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:

  • Para ( \widehat{G},\circ ) tworzy grupę, gdzie \circ jest składaniem permutacji.
  • Funkcja \widehat{\cdot}:G\longrightarrow\widehat{G} jest izomorfizmem grup ( G,\circ ) oraz ( \widehat{G},\circ ) .
  • \vert G \vert=\vert \widehat{G} \vert .
  • ( \widehat{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 \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

  • 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}( 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:

  • x_1^4 - jedyny taki obrót z jednoelementowymi cyklami to oczywiście id=( 0 )\!( 1 )\!( 2 )\!( 3 ) .
  • 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 ( 0 )\!( 123 ) , 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 ( 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