szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Kobieta
PostNapisane: 19 lis 2008, o 06:26 
Użytkownik

Posty: 1874
Lokalizacja: Lost Hope
Lemat Burnside'a powiada:

Jeśli grupa skończona G działa na zbiorze X, to liczba orbit tego działania N wyraża się suma:

N=\frac{1}{|G|}\sum_{g\in G}S(g)

gdzie S(g) jest liczba elementów zbioru \{x\in X: g(x)=x\},

czyli zbioru punktów stałych elementu g.

Lemat służy do zliczania rożnych obiektów z dokładnością do ich symetrii, obrotu etc.
Łatwo i automatycznie się go stosuje, bo na ogol wyznaczenie S(g) jest dużo prostsze od bezpośredniego wyznaczania N. Warto wiec poznać kilka grup skończonych, bo mogą ułatwić życie...

Przykład 1. Na ile sposobów, z dokładnością do obrotów, można pomalować wierzchołki 11-kata foremnego tak, by były 2 niebieskie, 2 zielone i 7 czerwonych wierzchołków?


Rozwiązanie: Wszystkich możliwych kolorowań (bez uwzględniania obrotów) jest \binom{11}{2}\binom{9}{2}=1980. Na zbiorze X tych wszystkich kolorowań, działa grupa cykliczna 11-elementowa, C_{11} obrotów o wielokrotności kata \frac{2\pi}{11}. Dla obrotu o kat 0, czyli o element neutralny, wszystkie kolorowania są punktami stałymi, zatem S(0)=1980. Pozostałe elementy grupy C_{11} nie maja żadnych punktów stałych:

Każdy element rożny od 0 generuje cala grupę C_{11}, gdyby wiec jakiś miał punkt stały, to również obrót jednostkowy o kat \frac{2\pi}{11} nie ruszałby tego kolorowania. Lecz wówczas wszystkie wierzchołki musiałyby być jednobarwne.

Zatem odpowiedzią na pytanie jest liczba: N=\frac{1}{|C_{11}|}\cdot S(0)=\frac{1}{11}\cdot 1980=180.

Przykład 2. Na ile sposobów, z dokładnością do izometrii, można pomalować wierzchołki 10-kata foremnego tak, by było 6 czarnych, 3 białe i 1 czerwony wierzchołek?

Rozwiązanie: Bez uwzględniania izometrii wierzchołki 10-kata foremnego można pokolorować zgodnie z warunkami na \binom{10}{1}\binom{9}{3}= 840 sposobów (wybieramy czerwony wierzchołek, a potem z reszty 3 białe).

Na zbiorze tych kolorowań, oznaczmy go X, działa grupa dihedralna 20-elementowa: D_{10}. Grupa ta składa się z 10 obrotów (w tym o kat 0, który oznaczamy symbolem 1): 1,o,o^2,...o^9 oraz 10 symetrii: s,so,so^2,...,so^9 - są to złożenia wielokrotności obrotu jednostkowego o kat \frac{\pi}{10} oznaczonego symbolem o, z jedna z symetrii 10-kata foremnego która oznaczamy symbolem s. Polowa tych symetrii nie ma żadnych stałych wierzchołków, są to symetrie względem symetralnych boków, druga polowa ma po 2 punkty stale będące naprzeciwległymi wierzchołkami lezącymi na osi symetrii.

Możemy teraz przystąpić do zliczania orbit: N.

Element neutralny 1 trzyma wszystkie kolorowania wiec S(1)=840. Jako ze jest tylko jeden wierzchołek koloru czerwonego, każda izometria nie ruszająca kolorowania musi mieć 1 wierzchołek stały. Takie izometrie to symetrie względem osi łączących naprzeciwlegle wierzchołki, których to symetrii jest 5, powiedzmy, ze są to \{s_1,s_2,s_3,s_3,s_5\}. Kolorowań stałych ze względu na taka symetrie jest tyle, ile osiowo symetrycznych kolorowań. Kolorowanie będące punktem stałym ma wiec biały wierzchołek naprzeciw czerwonego (bo białych jest 3) czyli takich kolorowań jest S(s_i)=8 dla i=1,2,3,4,5: na dwa sposoby można ustalić wzajemne połozenie wyróżnionych wierzchołków, białego i leżącego naprzeciw czerwonego, następnie wybieramy położenie jednego z dwóch pozostałych białych wierzchołków po jednej ze stron osi symetrii i reszta jest wyznaczona.

Mamy wiec już wszystkie dane do zastosowania lematu.

N=\frac{S(e)+S(s_1)+...+S(s_5)}{|D_{10}|}=\frac{840+5\cdot 8}{20}=44.

Przykład 3: Na ile sposobów, z dokładnością do izometrii, można pomalować ściany sześciennej kostki trzema kolorami tak, by naprzeciwlegle ściany były jednego koloru?

Rozwiązanie: Trzeba rozpracować grupę izometrii sześcianu. Jej elementy można opisać następująco:

Obrazem przekątnej sześcianu przy izometrii jest również przekątna. Wszystkich przekątnych jest 4, istnieje symetria przekształcająca jedna z przekątnych w dowolna inna bez ruszania pozostałych dwóch. Jest to symetria względem płaszczyzny zawierającej te dwie pozostałe przekątne. Zatem grupa izometrii sześcianu zawiera, jako podgrupę, grupę S_4 permutacji zbioru przekątnych. Żeby otrzymać pozostałe elementy grupy izometrii sześcianu, wystarczy złożyć jedna z tych permutacji (powstałych ze złożenia symetrii względem płaszczyzn zawierających pary przekątnych) z symetrią środkową względem środka sześcianu. Nietrudno się przekonać, ze to już wszystkie izometrie. Grupa izometrii sześcianu ma zatem postać S_4\times C_2.

Wszystkich kolorowań spełniających warunki zadania jest tyle, ile kolorowań ścian spotykających się w jednym z wierzchołków, czyli 27.

Teraz zbieramy dane o kolorowaniach stałych dla poszczególnych izometrii. Przyda nam się w tym celu pogrupowanie elementów S_4 w klasy sprzężoności:

  • identyczność (1 sztuka) \rightarrow 27 kolorowań stałych.
  • obroty o \pm\pi/2 wokół osi łączących środki ścian (6 sztuk) \rightarrow po 9 kolorowań stałych, para naprzeciwległych ścian przechodzi w siebie, pozostałe muszą być jednobarwne.
  • obroty o \pi wokół osi łączących środki przeciwległych ścian (3 sztuki) \rightarrow po 27 kolorowania stałych, bo zachowują przeciwlegle ściany.
  • obroty o \pi wokół osi łączących środki przeciwległych krawędzi (6 sztuk) \rightarrow po 9 kolorowania stałych, bo zachowują parę naprzeciwległych ścian, zaś pozostałe muszą być jednobarwne.
  • obroty wokół przekątnych sześcianu (o kat \frac{2\pi}{3} patrząc wzdłuż osi) (8 sztuk)\rightarrow po 3 kolorowania stale, bo wszystkie ściany muszą być jednego koloru.

N=\frac{1}{|S_4\times C_2|}\cdot 2\cdot (1\cdot 27+6\cdot 9+8\cdot 3+3\cdot 27+6\cdot 9+8\cdot 3)=\frac{528}{48}=11
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2019
Góra
Mężczyzna
PostNapisane: 19 lis 2008, o 20:37 
Gość Specjalny
Avatar użytkownika

Posty: 3306
Lokalizacja: Lebendigentanz
xiikzodz napisał(a):
Lemat Burnside'a powiada:

Jesli grupa skonczona G dziala na zbiorze X, to liczba orbit tego dzialania N wyraza sie suma:

N=\frac{1}{|G|}\sum_{g\in G}S(g)

gdzie S(g) jest liczba elementow zbioru \{x\in X: g(x)=x\},

czyli zbioru punktow stalych elementu g.
(...)


To jeszcze jakiś dowód można podać:

Najpierw drobne przygotowania:

(i)Zauważmy, że dla dowolnego x\in X zbiór \mbox{Stab}(x) = \{g\in G \ : \ g(x) = x\} z działaniem indukowanym z G jest podgrupą G.
Dowód:
1(x)= x czyli 1\in\mbox{Stab}(x), w szczególności \mbox{Stab}(x)\neq\emptyset.
Dla dowolnych a, b\in \mbox{Stab}(x) mamy
(ab^{-1})(x) = a(b^{-1}(x)) = a(b^{-1}(b(x))) = a((bb^{-1})(x)) = a(1(x)) = a(x) = x
(grupę \mbox{Stab}(x) nazywamy stabilizatorem elementu x).

(ii)Niech \Omega(x) = \{g(x) \ : \ g \in G\} (czyli \Omega(x) jest orbitą elementu x).
Mamy |\Omega(x)| = [G\ : \ \mbox{Stab}(x)].
Dowód:
Pokażemy, że funkcja \psi: \Omega(x)\ni g(x) \mapsto g\mbox{Stab}(x) \in G/\mbox{Stab}(x) jest bijekcją.
Injektywność i poprawna określoność:
Mamy \psi(g(x)) = \psi(h(x)) \iff g\mbox{Stab}(x) = h\mbox{Stab}(x) \iff h^{-1}g\in \mbox{Stab}(x).
Zatem jeśli \psi(g(x)) = \psi(h(x)) to:
h(x) = h((h^{-1}g)(x)) = (hh^{-1})(g(x)) = 1(g(x)) = g(x) (injektywność).
A jeśli h(x) = g(x), to:
(h^{-1}g)(x) = h^{-1}(g(x)) = h^{-1}(h(x)) = (h^{-1}h)(x) = 1(x) = x
czyli h^{-1}g\in \mbox{Stab}(x) czyli \psi(g(x)) = \psi(h(x)) (poprawna określoność).
Surjektywność jest natychmiastowa, bo dla dowolnego g\in G jest g\mbox{Stab}(x) = \psi(g(x)).

Teraz możemy przejść do dowodu lematu Burnside'a.
Niech \Omega_{1},\ldots, \Omega_{N} będą rozłącznymi orbitami działania G na X.
Zauważmy, że \forall_{x\in X, g\in G}\ g(x) = x \iff g\in \mbox{Stab}(x) (z definicji stabilizatora w (i)) oraz
\forall_{i=1,\ldots, N}\forall_{x,y\in \Omega_{i}} [G \ : \ \mbox{Stab}(x)] = |\Omega_{i}| = [G \ : \ \mbox{Stab}(y)] (z (ii))
Zatem dla każdego i = 1, \ldots, N:
\sum_{g\in G} |\{x\in \Omega_{i} : g(x) = x| = \mbox{Stab}(x_{0})\cdot [G \ : \ \mbox{Stab}(x_{0})] = |G|, gdzie x_{0} jest dowolnie ustalonym elementem \Omega_{i}.
Ponieważ \bigcup_{i=1}^{N}\Omega_{i} = X to:
\forall_{g\in G} \{x\in X \ : \ g(x) = x\} = \bigcup_{i=1}^{N}\{x\in \Omega_{i} \ : \ g(x) = x\}
a ponieważ wybrane orbity były rozłączne, to suma po prawej jest rozłączna, co daje dla dowolnego g\in G:
S(g) = \left|\bigcup_{i=1}^{N}\{x\in \Omega_{i} \ : \ g(x) = x\}\right| = \sum_{i =1}^{N}\left|\{x\in \Omega_{i} \ : \ g(x) = x\}\right|
i ostatecznie:
\sum_{g\in G}S(g) = \sum_{g\in G}\sum_{i =1}^{N}\left|\{x\in \Omega_{i} \ : \ g(x) = x\}\right| = \sum_{i =1}^{N}\sum_{g\in G}\left|\{x\in \Omega_{i} \ : \ g(x) = x\}\right| =   \sum_{i = 1}^{N}|G| = N|G|
\blacksquare
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Lemat Burnside'a - zadanie 6  Nesquik  0
 Lemat Burnside'a - zadanie 7  aGabi94  1
 Lemat Burnside'a - zadanie 3  kolotek  3
 Lemat Burnside'a - zadanie 8  laki00  1
 Lemat Burnside'a - zadanie 2  Anonymous  7
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl