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

Zastosowania teorii grup w zliczaniu

Ćwiczenie 1

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

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 $\left(G_{x},\circ \right)$ jest grupą. Ponieważ dla $g,h\in G_{x}$ mamy $g\!\left(x\right)=x=h\!\left(x\right)$, to

$\left(g\circ h\right)\!\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)=\left(g^{-1}\circ g\right)\!\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=\left\lbrace 1,2,\ldots ,12\right\rbrace$ będzie zbiorem indeksów wierzchołków $v_{1},v_{2},\ldots ,v_{12}$ dwudziestościanu foremnego. Ponadto niech $G$ będzie grupą obrotów (w $\mathbb {R} ^{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},\ldots ,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}{lp{5mm}l}{\text{obrót o}}\ 72^{\circ }{\text{:}}&&g_{1}=\left(1\right)\!\left(12\right)\!\left(2,3,4,5,6\right)\!\left(7,8,9,10,11\right),\\{\text{obrót o}}\ 144^{\circ }{\text{:}}&&g_{2}=\left(1\right)\!\left(12\right)\!\left(2,4,6,3,5\right)\!\left(7,9,11,8,10\right),\\{\text{obrót o}}\ 216^{\circ }{\text{:}}&&g_{3}=\left(1\right)\!\left(12\right)\!\left(2,5,3,6,4\right)\!\left(7,10,8,11,9\right),\\{\text{obrót o}}\ 288^{\circ }{\text{:}}&&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}=\left\lbrace id,g_{1},g_{2},g_{3},g_{4}\right\rbrace$ .

Ćwiczenie 3

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

$\left\vert G_{x}\right\vert =\left\vert G\left(x\rightarrow y\right)\right\vert =\left\vert G_{y}\right\vert$,

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

Wskazówka

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

Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \psi:G_x \ni g \longrightarrow h\circ g \in G\left( x\rightarrow y \right) }

oraz

Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \phi:G\left( x\rightarrow y \right) \ni g \longrightarrow g \circ h^{-1} \in G_y }

są bijekcjami.

Rozwiązanie

Elementy Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle x} oraz Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle y} należą do tej samej orbity, więc istnieje permutacja Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle h\in G} taka, że Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle h\!\left( x \right)=y} . Funkcja Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \psi} jest dobrze zdefiniowana, bo dla dowolnej permutacji Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle g\in G_x} mamy:

Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \left( h\circ g \right)\!\left( x \right)=h\!\left( g\!\left( x \right) \right)=h\!\left( x \right)=y} ,

czyli Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle h\circ g\in G\left( x\rightarrow y \right)} . Dla dowodu injektywności funkcji Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \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\left(x\rightarrow y\right)$ . Wtedy złożenie $h^{-1}\circ f$ spełnia

$\left(h^{-1}\circ f\right)\!\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 \!\left(h^{-1}\circ f\right)=h\circ h^{-1}\circ f=f$

Funkcja $\psi$ jest bijekcją pomiędzy $G_{x}$ oraz $G\left(x\rightarrow y\right)$ , więc $\left\vert G_{x}\right\vert =\left\vert G\left(x\rightarrow y\right)\right\vert$ . Bijektywność funkcji $\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 $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 {Z} _{6}$ :

${\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 $6$ permutacji postaci

$g_{k}\!\left(m\right)=m+k\mod 6\quad \quad$ dla $\ k,m=0,1,\ldots ,5$

Po rozłożeniu tych permutacji na cykle:

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

$\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ę $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}\left(x_{1},x_{2},x_{3},\ldots ,x_{n^{2}}\right)$ , 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 \left(n^{2}-1\right)\!\left(n^{2}\right)$ .
• $x_{2}^{n^{2}/2}$ - obrót o $180^{\circ }$ rozkładający się na cykle:

$\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)$

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

${\begin{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).\end{aligned}}$

Gdy $n$ jest nieparzyste, to ze względu na indeks $\zeta _{g}\left(x_{1},x_{2},x_{3},\ldots ,x_{n^{2}}\right)$ , obroty dzielą się na trzy - ale inne - typy:

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

$\left(\left(n^{2}+1\right)/2\right)\!\left(1,n^{2}\right)\!\left(2n^{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)$

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

${\begin{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).\end{aligned}}$

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

$\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 $n$ jest parzyste, oraz

$\zeta _{G}\left(x_{1},x_{2},x_{3},x_{4}\right)={\frac {1}{4}}\left(x_{1}^{n^{2}}+x_{1}x_{2}^{\left(n^{2}-1\right)/2}+2x_{1}x_{4}^{\left(n^{2}-1\right)/4}\right)$

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},\quad \quad \quad$ dla $\ n\$ parzystego,

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

Ćwiczenie 6

Niech $Y_{1}=\left\lbrace 0,1,2\right\rbrace$ , $Y_{2}=\left\lbrace 3,4,5\right\rbrace$ i $Y_{3}=\left\lbrace 6,7\right\rbrace$ . Policz liczbę kolorowań zbioru $\left\lbrace 0,1,\ldots ,7\right\rbrace$ 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{aligned}{\mathsf {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}+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{aligned}}$

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}{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:

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

$\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}^{2}x_{2}^{2}+4x_{2}^{3}+2x_{3}^{2}+2x_{6}\right)$

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}\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+3r^{4}g^{2}+3r^{3}g^{3}+3r^{2}g^{4}+rg^{5}+g^{6}\end{array}}$

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