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 (x) = x = h (x)$ , to

(g \circ h) (x) = g (h (x)) = g (x) = x .

oraz

g^{- 1} (x) = g^{- 1} (g (x)) = (g^{- 1} \circ g) (x) = i d (x) = 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 $ℝ^{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:

$i d = (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11) (12),$

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} = {i d, g_{1}, g_{2}, g_{3}, g_{4}}$ .

Ćwiczenie 3

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

| G_{x} | = | G (x \to y) | = | G_{y} |,

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

Wskazówka

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

ψ : G_{x} ∋ g ⟶ h \circ g \in G (x \to y)

oraz

ϕ : G (x \to y) ∋ 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 (x) = y$ . Funkcja $ψ$ jest dobrze zdefiniowana, bo dla dowolnej permutacji $g \in G_{x}$ mamy:

(h \circ g) (x) = h (g (x)) = h (x) = y,

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

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

Dla dowodu surjektywności funkcji $ψ$ 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) (x) = h^{- 1} (f (x)) = h^{- 1} (y) = x,

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

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

Funkcja $ψ$ jest bijekcją pomiędzy $G_{x}$ oraz $G (x \to y)$ , więc $| G_{x} | = | G (x \to y) |$ . Bijektywność funkcji $ϕ$ 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} (m) = m + k m o d

6 .

Rozwiązanie

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

{Sześciokąt.Rysunek z pliku:polyszesciokat.eps}

obrót o $24 0^{\circ}$ zgodnie z ruchem wskazówek zegara, to następująca permutacja zbioru indeksów $ℤ_{6}$ :

\begin{array}{rclcrcl} 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} (m) = m + k mod 6

dla

k, m = 0, 1, \dots, 5 .

Po rozłożeniu tych permutacji na cykle:

\begin{array}{rclcrcl} g_{0} & = (0) (1) (2) (3) (4) (5), & g_{3} & = (03) (14) (25), \\ g_{1} & = (012345), & g_{4} & = (042) (153), \\ g_{2} & = (024) (135), & g_{5} & = (054321) \end{array}

otrzymujemy indeks grupy obrotów:

ζ_{G} (x_{1}, x_{2}, \dots, x_{6}) = \frac{1}{6} (x_{1}^{6} + x_{2}^{3} + 2 x_{3}^{2} + 2 x_{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

Rozwiązanie

Ponumerujmy pola szachownicy tak, jak na rysunku 3.

{rys. 3 Ponumerowana szachownica rozmiarów $n \times n$ .. Rysunek z pliku:polyszachownica.eps}

Gdy $n$ jest parzyste, to ze względu na indeks $ζ_{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: $(1) (2) (3) \dots (n^{2} - 1) (n^{2})$ .
$x_{2}^{n^{2} / 2}$ - obrót o $18 0^{\circ}$ rozkładający się na cykle:

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

$x_{4}^{n^{2} / 4}$ - dwa obroty o $9 0^{\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 $ζ_{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 $18 0^{\circ}$ rozkładający się tym razem na cykle:

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

$x_{1} x_{4}^{(n^{2} - 1) / 4}$ - dwa obroty o $9 0^{\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:

ζ_{G} (x_{1}, x_{2}, x_{3}, x_{4}) = \frac{1}{4} (x_{1}^{n^{2}} + x_{2}^{n^{2} / 2} + 2 x_{4}^{n^{2} / 4})

jeśli $n$ jest parzyste, oraz

ζ_{G} (x_{1}, x_{2}, x_{3}, x_{4}) = \frac{1}{4} (x_{1}^{n^{2}} + x_{1} x_{2}^{(n^{2} - 1) / 2} + 2 x_{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

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ść $6 0^{\circ}$ względem osi prostopadłej do płaszczyzny, w której leży sześciokąt,
obroty o $18 0^{\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}{rclcrcl} g_{0} & = (0) (1) (2) (3) (4) (5), & g_{3} & = (03) (14) (25), \\ g_{1} & = (012345), & g_{4} & = (042) (153), \\ g_{2} & = (024) (135), & g_{5} & = (054321) . \end{array}

Zaś permutacje drugiego typu, to symetrie osiowe:

\begin{array}{rclcrcl} g_{6} & = (05) (14) (23), & g_{9} & = (0) (3) (15) (24), \\ g_{7} & = (03) (12) (45), & g_{10} & = (1) (4) (02) (35), \\ g_{8} & = (01) (25) (34), & g_{11} & = (2) (5) (13) (04) . \end{array}

Indeks grupy wynosi więc

ζ_{G} (x_{1}, x_{2}, x_{3}, x_{4}, x_{5}, x_{6}) = \frac{1}{12} (x_{1}^{6} + 3 x_{1}^{2} x_{2}^{2} + 4 x_{2}^{3} + 2 x_{3}^{2} + 2 x_{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} ζ_{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 + 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ą $3$ różne naszyjniki z $4$ koralików czerwonych i $2$ zielonych.

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

Zastosowania teorii grup w zliczaniu

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia