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

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:

$\begin{array}{lll}\text{obrót o}72^{\circ }\text{:}& & g_1=\left(1\right)\left(12\right)(2,3,4,5,6)(7,8,9,10,11),\\ \text{obrót o}144^{\circ }\text{:}& & g_2=\left(1\right)\left(12\right)(2,4,6,3,5)(7,9,11,8,10),\\ \text{obrót o}216^{\circ }\text{:}& & g_3=\left(1\right)\left(12\right)(2,5,3,6,4)(7,10,8,11,9),\\ \text{obrót o}288^{\circ }\text{:}& & g_4=\left(1\right)\left(12\right)(2,6,5,4,3)(7,11,10,9,8).\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 $f\in G(x\to y)$ . 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

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

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:

$\begin{array}{rlr}& & (1,n,n^2,(n-1)n+1)(2,2n,n^2-1,(n-2)n+1)\cdots \\ & & \cdots ((n-1)\frac{n}{2},(n-1)\frac{n}{2}+1,(n+1)\frac{n}{2},(n+1)\frac{n}{2}+1).\end{array}$

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:

$\begin{array}{rlr}& & ((n^2+1)/2)(1,n,n^2,(n-1)n+1)(2,2n,n^2-1,(n-2)n+1)\cdots \\ & & \cdots ({(n-1)}^2/2-1,{(n-1)}^2/2+1,{(n+1)}^2/2+1,{(n+1)}^2/2-1).\end{array}$

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 ${\displaystyle }$

Ć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 5.8.

Rozwiązanie

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

$\begin{array}{rl}{\mathsf{U}}_D(r,g,b)& =\prod _{i=1}^3(r^{\left|Y_i\right|}+g^{\left|Y_i\right|}+b^{\left|Y_i\right|})\\ & =(r^3+g^3+b^3)\cdot (r^3+g^3+b^3)\cdot (r^2+g^2+b^2)\\ & =r^8+r^6{g}^2+2r^5{g}^3+2r^3{g}^5+r^2{g}^6+g^8+r^6{b}^2+2r^3{g}^3{b}^2\\ & +g^6{b}^2+2r^5{b}^3+2r^3{g}^2{b}^3+2r^2{g}^3{b}^3+2g^5{b}^3+2r^3{b}^5+2g^3{b}^5\\ & +r^2{b}^6+g^2{b}^6+b^8\end{array}$

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.