Matematyka dyskretna 2/Ćwiczenia 5: Zastosowania teorii grup w zliczaniu

From Studia Informatyczne

Zastosowania teorii grup w zliczaniu

Ćwiczenie 1

Pokaż, że dla G-zbioru \displaystyle \left( G,X \right) oraz \displaystyle x\in X , stabilizator elementu \displaystyle x wraz z składaniem, tzn. \displaystyle \left( G_x,\circ \right) jest podgrupą grupy \displaystyle \left( G,\circ \right) .

Wskazówka

Wystarczy sprawdzić, czy dla \displaystyle g, h\in G_x , złożenie \displaystyle g\circ h oraz element odwrotny \displaystyle g^{-1} należą do \displaystyle G_x .

Rozwiązanie

Zbiór \displaystyle G_x jest podzbiorem \displaystyle G , więc wystarczy sprawdzić, że \displaystyle \left( G_x,\circ \right) jest grupą. Ponieważ dla \displaystyle g, h\in G_x mamy \displaystyle g\!\left( x \right)=x=h\!\left( x \right), to


\displaystyle \left( g\circ h \right)\!\left( x \right)  = g\!\left( h\!\left( x \right) \right) = g\!\left( x \right)=x.


oraz


\displaystyle g^{-1}\!\left( x \right)=g^{-1}\!\left( g\!\left( x \right) \right)  = \left( g^{-1}\circ g \right)\!\left( x \right)  = id\!\left( x \right) = x,


a zatem \displaystyle g\circ h\in G_x oraz \displaystyle g^{-1}\in G_x .

Ćwiczenie 2

Niech \displaystyle X=\left\lbrace 1,2,\ldots,12 \right\rbrace będzie zbiorem indeksów wierzchołków \displaystyle v_1,v_2,\ldots,v_{12} dwudziestościanu foremnego. Ponadto niech \displaystyle G będzie grupą obrotów (w \displaystyle \mathbb{R}^3 ) tego dwudziestościanu. Przedstaw stabilizator wierzchołka \displaystyle v_1 w działaniu grupy permutacji \displaystyle G na zbiorze \displaystyle X i rozłóż permutacje z tego stabilizatora na cykle.

Wskazówka

Jedynie identyczność oraz obroty wokół osi przechodzącej przez wierzchołek \displaystyle v_1 nie zmieniają położenia tego wierzchołka.

Rozwiązanie

<flash>file=Cw poly icosahedron.swf|width=250|height=250</flash>

Dwudziestościan foremny o wierzchołkach \displaystyle v_1,v_2,\ldots,v_{12}

Jeżeli oś obrotu nie przechodzi przez wierzchołek \displaystyle v_1 , to po obrocie \displaystyle v_1 zmieni swoje położenie. A zatem jedynie identyczność oraz obroty wokół osi przechodzącej przez wierzchołek \displaystyle v_1 nie zmieniają położenia tego wierzchołka.

Identyczność ma oczywiście rozkład:


\displaystyle id=\left( 1 \right)\!\left( 2 \right)\!\left( 3 \right)\!\left( 4 \right)\!\left( 5 \right)\!\left( 6 \right)\!\left( 7 \right)\!\left( 8 \right)\!\left( 9 \right)\!\left( 10 \right)\!\left( 11 \right)\!\left( 12 \right),


podczas gdy obroty maja rozkład:


\displaystyle \begin{array} {lp{5mm}l} \textrm{obrót o}\ 72^{\circ}\textrm{:}&&g_1=\left( 1 \right)\!\left( 12 \right)\!\left( 2,3,4,5,6 \right)\!\left( 7,8,9,10,11 \right),\\ \textrm{obrót o}\ 144^{\circ}\textrm{:}&&g_2=\left( 1 \right)\!\left( 12 \right)\!\left( 2,4,6,3,5 \right)\!\left( 7,9,11,8,10 \right),\\ \textrm{obrót o}\ 216^{\circ}\textrm{:}&&g_3=\left( 1 \right)\!\left( 12 \right)\!\left( 2,5,3,6,4 \right)\!\left( 7,10,8,11,9 \right),\\ \textrm{obrót o}\ 288^{\circ}\textrm{:}&&g_4=\left( 1 \right)\!\left( 12 \right)\!\left( 2,6,5,4,3 \right)\!\left( 7,11,10,9,8 \right). \end{array}


A zatem stabilizator \displaystyle 1 -ki to \displaystyle G_1=\left\lbrace id,g_1,g_2,g_3,g_4 \right\rbrace .

Ćwiczenie 3

Pokaż, że dla G-zbioru \displaystyle \left( G,X \right) zachodzi


\displaystyle \left\vert G_x \right\vert=\left\vert G\left( x\rightarrow y \right) \right\vert=\left\vert G_y \right\vert,


gdzie \displaystyle x,y\in Gx\subseteq X .

Wskazówka

Gdy \displaystyle h\in G spełnia \displaystyle h\!\left( x \right)=y , to


\displaystyle \psi:G_x \ni g \longrightarrow h\circ g \in G\left( x\rightarrow y \right)


oraz


\displaystyle \phi:G\left( x\rightarrow y \right) \ni g \longrightarrow g \circ h^{-1} \in G_y


są bijekcjami.

Rozwiązanie

Elementy \displaystyle x oraz \displaystyle y należą do tej samej orbity, więc istnieje permutacja \displaystyle h\in G taka, że \displaystyle h\!\left( x \right)=y . Funkcja \displaystyle \psi jest dobrze zdefiniowana, bo dla dowolnej permutacji \displaystyle g\in G_x mamy:


\displaystyle \left( h\circ g \right)\!\left( x \right)=h\!\left( g\!\left( x \right) \right)=h\!\left( x \right)=y,


czyli \displaystyle h\circ g\in G\left( x\rightarrow y \right) . Dla dowodu injektywności funkcji \displaystyle \psi załóżmy, że \displaystyle h\circ g = \psi\!\left( g \right) = \psi\!\left( f \right) = h\circ f . Wtedy


\displaystyle g = h^{-1} \circ h\circ g = h^{-1} \circ h\circ f = f.


Dla dowodu surjektywności funkcji \displaystyle \psi niech \displaystyle f\inG\left( x\rightarrow y \right) . Wtedy złożenie \displaystyle h^{-1}\circ f spełnia


\displaystyle \left( h^{-1}\circ f \right)\!\left( x \right)=h^{-1}\!\left( f\!\left( x \right) \right)=h^{-1}\!\left( y \right)=x,


czyli \displaystyle h^{-1}\circ f \in G_x . Ponadto


\displaystyle \psi\!\left( h^{-1}\circ f \right)=h\circ h^{-1}\circ f = f.


Funkcja \displaystyle \psi jest bijekcją pomiędzy \displaystyle G_x oraz \displaystyle G\left( x\rightarrow y \right) , więc \displaystyle \left\vert G_x \right\vert=\left\vert G\left( x\rightarrow y \right) \right\vert . Bijektywność funkcji \displaystyle \phi pokazuje się analogicznie.

Ćwiczenie 4

Przedstaw indeks grupy obrotów sześciokąta.

Wskazówka

Obroty sześciokąta odpowiadają następującym permutacjom zbioru \displaystyle Z_6 :


\displaystyle g_k\!\left( m \right)= m+k  mod \displaystyle   6.


Rozwiązanie

<flash>file=Poly szesciokat.swf|width=250|height=250</flash>

Sześciokąt


Numerując wierzchołki sześciokąta jak rysunku 2, widzimy, że np.:

obrót o \displaystyle 240^{\circ} zgodnie z ruchem wskazówek zegara,

to następująca permutacja zbioru indeksów \displaystyle \mathbb{Z}_6 :


\displaystyle \begin{array} {rclp{2cm}rcl} 0&\rightarrow 4,&&3&\rightarrow 1,\\ 1&\rightarrow 5,&&4&\rightarrow 2,\\ 2&\rightarrow 0,&&5&\rightarrow 3. \end{array}


W ogólności mamy \displaystyle 6 permutacji postaci


\displaystyle g_k\!\left( m \right)= m+k \mod 6\quad\quad dla \displaystyle  \ k,m=0,1,\ldots,5.


Po rozłożeniu tych permutacji na cykle:


\displaystyle \begin{array} {rclp{2cm}rcl} g_0&=\left( 0 \right)\!\left( 1 \right)\!\left( 2 \right)\!\left( 3 \right)\!\left( 4 \right)\!\left( 5 \right),&&g_3&=\left( 03 \right)\!\left( 14 \right)\!\left( 25 \right),\\ g_1&=\left( 012345 \right),&&g_4&=\left( 042 \right)\!\left( 153 \right),\\ g_2&=\left( 024 \right)\!\left( 135 \right),&&g_5&=\left( 054321 \right)  \end{array}


otrzymujemy indeks grupy obrotów:


\displaystyle \zeta_{G}\left( x_1,x_2,\ldots,x_6 \right)=\frac{1}{6}\left( x_1^6+x_2^3+2x_3^2+2x_6 \right).


Ćwiczenie 5

Policz na ile różnych sposobów można pokolorować szachownicę \displaystyle n\times n dwoma kolorami. Szachownica nie ma wyróżnionych boków, więc dwu kolorowań nie można rozróżnić poprzez jej obrót względem osi do niej prostopadłej.

Wskazówka

Policz indeks grupy obrotów

i zastosuj Twierdzenie 5.7.

Rozwiązanie

<flash>file=Poly szachownica.swf|width=250|height=250</flash>

Rys 3: Ponumerowana szachownica rozmiarów \displaystyle n\times n


Ponumerujmy pola szachownicy tak, jak na rysunku 3.

Gdy \displaystyle n jest parzyste, to ze względu na indeks

\displaystyle \zeta_{g}\left( x_1,x_2,x_3,\ldots,x_{n^2} \right) , obroty dzielą się na trzy typy:

  • \displaystyle x_1^{n^2} - identyczność rozkładająca się na cykle: \displaystyle \left( 1 \right)\!\left( 2 \right)\!\left( 3 \right)\cdots\left( n^2-1 \right)\!\left( n^2 \right) .
  • \displaystyle x_2^{n^2/2} - obrót o \displaystyle 180^{\circ} rozkładający się na cykle:

\displaystyle \left( 1,n^2 \right)\!\left( 2, n^2-1 \right)\!\left( 3,n^2-2 \right)\cdots\left( n^2/2,n^2/2+1 \right).

  • \displaystyle x_4^{n^2/4} - dwa obroty o \displaystyle 90^{\circ} ; obrót zgodny z ruchem zegara rozkłada się na cykle:

\displaystyle \aligned &&\left( 1,n,n^2,\left( n-1 \right)n+1 \right)\!\left( 2,2n,n^2-1,\left( n-2 \right)n+1 \right)\cdots\\ &&\quad\quad\quad\quad\quad\quad\cdots\left( \left( n-1 \right)\frac{n}{2},\left( n-1 \right)\frac{n}{2}+1,\left( n+1 \right)\frac{n}{2},\left( n+1 \right)\frac{n}{2}+1 \right). \endaligned

Gdy \displaystyle n jest nieparzyste, to ze względu na indeks

\displaystyle \zeta_{g}\left( x_1,x_2,x_3,\ldots,x_{n^2} \right) , obroty dzielą się na trzy - ale inne - typy:

  • \displaystyle x_1^{n^2} - identyczność.
  • \displaystyle x_1x_2^{\left( n^2-1 \right)/2} - obrót o \displaystyle 180^{\circ} rozkładający się tym razem na cykle:

\displaystyle \left( \left( n^2+1 \right)/2 \right)\!\left( 1,n^2 \right)\!\left( 2 n^2-1 \right)\!\left( 3,n^2-2 \right)\cdots\left( \left( n-1 \right)^2/2-1,\left( n+1 \right)^2/2+1 \right).

  • \displaystyle x_1x_4^{\left( n^2-1 \right)/4} - dwa obroty o \displaystyle 90^{\circ} ; obrót zgodny z ruchem zegara rozkłada się na cykle:


\displaystyle \aligned &&\left( \left( n^2+1 \right)/2 \right)\!\left( 1,n,n^2,\left( n-1 \right)n+1 \right)\!\left( 2,2n,n^2-1,\left( n-2 \right)n+1 \right)\cdots\\ &&\quad\cdots\left( \left( n-1 \right)^2/2-1,\left( n-1 \right)^2/2+1,\left( n+1 \right)^2/2+1,\left( n+1 \right)^2/2-1 \right). \endaligned


Indeks grupy obrotów szachownicy \displaystyle n\times n jest więc równy:


\displaystyle \zeta_{G}\left( x_1,x_2,x_3,x_4 \right)=\frac{1}{4}\left( x_1^{n^2}+x_2^{n^2/2}+2x_4^{n^2/4} \right)


jeśli \displaystyle n jest parzyste, oraz


\displaystyle \zeta_{G}\left( x_1,x_2,x_3,x_4 \right)=\frac{1}{4}\left( x_1^{n^2}+x_1x_2^{\left( n^2-1 \right)/2}+2x_1x_4^{\left( n^2-1 \right)/4} \right)


dla \displaystyle n nieparzystego. Tak więc, Twierdzenie 5.7 daje, że liczba (nierozróżnialnych względem obrotów) pokolorowań szachownicy \displaystyle n\times n wynosi


\displaystyle \frac{1}{4}2^{n^2}+\frac{1}{4}2^{n^2/2}+\frac{1}{2}2^{n^2/4},\quad\quad\quad dla \displaystyle  \ n\ parzystego,


\displaystyle \frac{1}{4}2^{n^2}+\frac{1}{4}2^{\left( n^2+1 \right)/2}+\frac{1}{2}2^{\left( n^2+3 \right)/4},\quad dla \displaystyle  \ n\ nieparzystego \displaystyle  .


Ćwiczenie 6

Niech \displaystyle Y_1=\left\lbrace 0,1,2 \right\rbrace , \displaystyle Y_2=\left\lbrace 3,4,5 \right\rbrace i \displaystyle Y_3=\left\lbrace 6,7 \right\rbrace . Policz liczbę kolorowań zbioru \displaystyle \left\lbrace 0,1,\ldots,7 \right\rbrace spełniających warunki:

  • elementy zbioru \displaystyle Y_i są jednobarwne,
  • \displaystyle 3 elementy są pokolorowane na czerwono, \displaystyle 2 elementy są pokolorowane na zielono, \displaystyle 3 elementy są pokolorowane na niebiesko.

Wskazówka

Warto skorzystać z Twierdzenia 5.8.

Rozwiązanie

Korzystając z Twierdzenia 5.8, problem sprowadza się do odczytania współczynnika przy jednomianie \displaystyle r^3g^2b^3 w funkcji tworzącej


\displaystyle \aligned {\sf U}_{D}\left( r,g,b \right)&=\prod_{i=1}^3\left( r^{\left\vert Y_i \right\vert} +g^{\left\vert Y_i \right\vert} + b^{\left\vert Y_i \right\vert} \right)\\ &=\left( r^3 + g^3 + b^3 \right)\cdot\left( r^3 + g^3 + b^3 \right)\cdot\left( r^2 + g^2 + b^2 \right)\\ &=r^8 + r^6 g^2 + 2 r^5 g^3 + 2 r^3 g^5 + r^2 g^6 + g^8 + r^6 b^2 + 2 r^3 g^3 b^2\\  & + g^6 b^2 + 2 r^5 b^3 + 2 r^3 g^2 b^3 + 2 r^2 g^3 b^3 + 2 g^5 b^3 + 2 r^3 b^5 + 2 g^3 b^5\\  & + r^2 b^6 + g^2 b^6 + b^8 \endaligned


W efekcie uzyskujemy, że są \displaystyle 2 różne kolorowania spełniające warunki zadania.

Ćwiczenie 7

Na ile sposobów można spiąć w naszyjnik \displaystyle 4 korale czerwone i \displaystyle 2 zielone.

Wskazówka

Zauważ, że pytamy o to, na ile nierożróżnialnych sposobów można pokolorować wierzchołki sześciokąta foremnego tak, by \displaystyle 4 były czerwone, a \displaystyle 2 zielone.

Rozwiązanie

Kolorowania są nierozróżnialne, jeśli jedno można otrzymać przez z drugiego poprzez obrót naszyjnika lub spojrzenie nań z drugiej strony. A zatem zmiany położenia sześciokąta to

  • obroty o wielokrotność \displaystyle 60^{\circ} względem osi prostopadłej do płaszczyzny, w której leży sześciokąt,
  • obroty o \displaystyle 180^{\circ} względem osi przechodzącej przez środki przeciwległych boków

lub przeciwległych wierzchołków.

Korzystając z Ćwiczenie 4 wiemy już,

że permutacje pierwszego typu to


\displaystyle \begin{array} {rclp{2cm}rcl} g_0&=\left( 0 \right)\!\left( 1 \right)\!\left( 2 \right)\!\left( 3 \right)\!\left( 4 \right)\!\left( 5 \right),&&g_3&=\left( 03 \right)\!\left( 14 \right)\!\left( 25 \right),\\ g_1&=\left( 012345 \right),&&g_4&=\left( 042 \right)\!\left( 153 \right),\\ g_2&=\left( 024 \right)\!\left( 135 \right),&&g_5&=\left( 054321 \right).  \end{array}


Zaś permutacje drugiego typu, to symetrie osiowe:


\displaystyle \begin{array} {rclp{2cm}rcl} g_6&=\left( 05 \right)\!\left( 14 \right)\!\left( 23 \right),&&g_9&=\left( 0 \right)\!\left( 3 \right)\!\left( 15 \right)\!\left( 24 \right),\\ g_7&=\left( 03 \right)\!\left( 12 \right)\!\left( 45 \right),&&g_{10}&=\left( 1 \right)\!\left( 4 \right)\!\left( 02 \right)\!\left( 35 \right),\\ g_8&=\left( 01 \right)\!\left( 25 \right)\!\left( 34 \right),&&g_{11}&=\left( 2 \right)\!\left( 5 \right)\!\left( 13 \right)\!\left( 04 \right).  \end{array}


Indeks grupy wynosi więc


\displaystyle \zeta_{G}\left( x_1,x_2,x_3,x_4,x_5,x_6 \right)=\frac{1}{12}\left( x_1^6+3x_1^2x_2^2+4x_2^3+2x_3^2+2x_6 \right).


Na mocy Twierdzenia 5.9 wystarczy więc, za \displaystyle x_i , w indeksie grupy, podstawić \displaystyle r^i+g^i i po przerachowaniu odczytać współczynnik stojący przy \displaystyle r^4g^2 :


\displaystyle \begin{array} {l} \zeta_{G}\left( r+g,\ r^2+g^2,\ r^3+g^3,\ r^4+g^4,\ r^5+g^5,\ r^6+g^6 \right)\ =\\ =\ \frac{1}{12}\left( (r + g)^6 + 3(r + g)^2(r^2 + g^2)^2 + 4(r^2 + g^2)^3 + 2(r^3 + g^3)^2 +    2(r^6 + g^6) \right)\\ =\  r^6 +  r^5 g + 3 r^4 g^2 + 3 r^3 g^3 + 3 r^2 g^4 +  r g^5 +  g^6 \end{array}


A zatem są \displaystyle 3 różne naszyjniki z \displaystyle 4 koralików czerwonych i \displaystyle 2 zielonych.