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

Zastosowania teorii grup w zliczaniu

Ćwiczenie 1

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

Wskazówka

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

Rozwiązanie

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

$(g\circ h)\left(x\right)=g\left(h\left(x\right)\right)=g\left(x\right)=x.$

oraz

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

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

Ćwiczenie 2

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

Wskazówka

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

Rozwiązanie

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

<div.thumbcaption>Dwudziestościan foremny o wierzchołkach $v_1,v_2,\dots ,v_{12}$

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

Identyczność ma oczywiście rozkład:

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

Parser nie mógł rozpoznać (nieznana funkcja „\begin{array}”): {\displaystyle \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 $1$ -ki to $G_1=\{id,g_1,g_2,g_3,g_4\}$ .

Ćwiczenie 3

Pokaż, że dla G-zbioru $(G,X)$ zachodzi

$\left|G_x\right|=\left|G(x\to y)\right|=\left|G_y\right|,$

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

Wskazówka

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

$\psi :G_x\ni g⟶h\circ g\in G(x\to y)$

oraz

$\varphi :G(x\to y)\ni g⟶g\circ h^{-1}\in G_y$

są bijekcjami.

Rozwiązanie

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

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

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

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

Dla dowodu surjektywności funkcji $\psi$ niech Parser nie mógł rozpoznać (nieznana funkcja „\inG”): {\displaystyle \displaystyle f\inG\left( x\rightarrow y \right) } . Wtedy złożenie $h^{-1}\circ f$ spełnia

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

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

$\psi (h^{-1}\circ f)=h\circ h^{-1}\circ f=f.$

Funkcja $\psi$ jest bijekcją pomiędzy $G_x$ oraz $G(x\to y)$ , więc $\left|G_x\right|=\left|G(x\to y)\right|$ . Bijektywność funkcji $\varphi$ 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 $Z_6$ :

$g_k\left(m\right)=m+kmod$ $6.$

Rozwiązanie

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

<div.thumbcaption>Sześciokąt

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

obrót o $240^{\circ }$ zgodnie z ruchem wskazówek zegara, to następująca permutacja zbioru indeksów ${\mathbb{\mathbb{Z}}}_6$ :

$\begin{array}{rclcr}0& \to 4,& & 3& \to 1,\\ 1& \to 5,& & 4& \to 2,\\ 2& \to 0,& & 5& \to 3.\end{array}$

W ogólności mamy $6$ permutacji postaci

$g_k\left(m\right)=m+kmod6$ dla $k,m=0,1,\dots ,5.$

Po rozłożeniu tych permutacji na cykle:

$\begin{array}{rclcr}{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:

${\zeta }_G(x_1,x_2,\dots ,x_6)=\frac{1}{6}(x_1^6+x_2^3+2x_3^2+2x_6).$

Ćwiczenie 5

Policz na ile różnych sposobów można pokolorować szachownicę $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>

<div.thumbcaption>Rys 3: Ponumerowana szachownica rozmiarów $n\times n$

Ponumerujmy pola szachownicy tak, jak na rysunku 3.

Gdy $n$ jest parzyste, to ze względu na indeks ${\zeta }_g(x_1,x_2,x_3,\dots ,x_{n^2})$ , obroty dzielą się na trzy typy:

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

$(1,n^2)(2,n^2-1)(3,n^2-2)\cdots (n^2/2,n^2/2+1).$

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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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 $n$ jest nieparzyste, to ze względu na indeks ${\zeta }_g(x_1,x_2,x_3,\dots ,x_{n^2})$ , obroty dzielą się na trzy - ale inne - typy:

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

$((n^2+1)/2)(1,n^2)(2n^2-1)(3,n^2-2)\cdots ({(n-1)}^2/2-1,{(n+1)}^2/2+1).$

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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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 $n\times n$ jest więc równy:

${\zeta }_G(x_1,x_2,x_3,x_4)=\frac{1}{4}(x_1^{n^2}+x_2^{n^2/2}+2x_4^{n^2/4})$

jeśli $n$ jest parzyste, oraz

${\zeta }_G(x_1,x_2,x_3,x_4)=\frac{1}{4}(x_1^{n^2}+x_1{x}_2^{(n^2-1)/2}+2x_1{x}_4^{(n^2-1)/4})$

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

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

$\frac{1}{4}{2}^{n^2}+\frac{1}{4}{2}^{(n^2+1)/2}+\frac{1}{2}{2}^{(n^2+3)/4},$ dla $n$ nieparzystego $.$

Ćwiczenie 6

Niech $Y_1=\{0,1,2\}$ , $Y_2=\{3,4,5\}$ i $Y_3=\{6,7\}$ . Policz liczbę kolorowań zbioru $\{0,1,\dots ,7\}$ spełniających warunki:

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

Wskazówka

Warto skorzystać z twierdzenia [th][th U=()*()*()].

Rozwiązanie

Korzystając z twierdzenia [th][th U=()*()*()], problem sprowadza się do odczytania współczynnika przy jednomianie $r^3{g}^2{b}^3$ w funkcji tworzącej

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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ą $2$ różne kolorowania spełniające warunki zadania.

Ćwiczenie 7

Na ile sposobów można spiąć w naszyjnik $4$ korale czerwone i $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 $4$ były czerwone, a $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ść $60^{\circ }$ względem osi prostopadłej do płaszczyzny, w której leży sześciokąt,
• obroty o $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

$\begin{array}{rclcr}{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:

$\begin{array}{rclcr}{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

${\zeta }_G(x_1,x_2,x_3,x_4,x_5,x_6)=\frac{1}{12}(x_1^6+3x_1^2{x}_2^2+4x_2^3+2x_3^2+2x_6).$

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

$\begin{array}{l}{\zeta }_G(r+g,r^2+g^2,r^3+g^3,r^4+g^4,r^5+g^5,r^6+g^6)=\\ =\frac{1}{12}((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))\\ =r^6+r^{5}g+3r^4{g}^2+3r^3{g}^3+3r^2{g}^4+r{g}^5+g^6\end{array}$

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