Lemat Burnside'a

Zbiór wzorów, definicji i najczęściej poruszanych problemów z Algebry.
xiikzodz
Użytkownik
Użytkownik
Posty: 1874
Rejestracja: 4 paź 2008, o 02:13
Płeć: Kobieta
Lokalizacja: Lost Hope
Podziękował: 28 razy
Pomógł: 502 razy

Lemat Burnside'a

Post autor: xiikzodz »

Lemat Burnside'a powiada:

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

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

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

czyli zbioru punktów stałych elementu \(\displaystyle{ 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 \(\displaystyle{ S(g)}\) jest dużo prostsze od bezpośredniego wyznaczania \(\displaystyle{ 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 \(\displaystyle{ 11}\)-kata foremnego tak, by były \(\displaystyle{ 2}\) niebieskie, \(\displaystyle{ 2}\) zielone i \(\displaystyle{ 7}\) czerwonych wierzchołków?


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

Każdy element rożny od \(\displaystyle{ 0}\) generuje cala grupę \(\displaystyle{ C_{11}}\), gdyby wiec jakiś miał punkt stały, to również obrót jednostkowy o kat \(\displaystyle{ \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: \(\displaystyle{ 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 \(\displaystyle{ \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 \(\displaystyle{ X}\), działa grupa dihedralna 20-elementowa: \(\displaystyle{ D_{10}}\). Grupa ta składa się z 10 obrotów (w tym o kat 0, który oznaczamy symbolem \(\displaystyle{ 1}\)): \(\displaystyle{ 1,o,o^2,...o^9}\) oraz 10 symetrii: \(\displaystyle{ s,so,so^2,...,so^9}\) - są to złożenia wielokrotności obrotu jednostkowego o kat \(\displaystyle{ \frac{\pi}{10}}\) oznaczonego symbolem \(\displaystyle{ o}\), z jedna z symetrii \(\displaystyle{ 10}\)-kata foremnego która oznaczamy symbolem \(\displaystyle{ s}\). Polowa tych symetrii nie ma żadnych stałych wierzchołków, są to symetrie względem symetralnych boków, druga polowa ma po \(\displaystyle{ 2}\) punkty stale będące naprzeciwległymi wierzchołkami lezącymi na osi symetrii.

Możemy teraz przystąpić do zliczania orbit: \(\displaystyle{ N}\).

Element neutralny \(\displaystyle{ 1}\) trzyma wszystkie kolorowania wiec \(\displaystyle{ S(1)=840}\). Jako ze jest tylko jeden wierzchołek koloru czerwonego, każda izometria nie ruszająca kolorowania musi mieć \(\displaystyle{ 1}\) wierzchołek stały. Takie izometrie to symetrie względem osi łączących naprzeciwlegle wierzchołki, których to symetrii jest \(\displaystyle{ 5}\), powiedzmy, ze są to \(\displaystyle{ \{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 \(\displaystyle{ 3}\)) czyli takich kolorowań jest \(\displaystyle{ S(s_i)=8}\) dla \(\displaystyle{ 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.

\(\displaystyle{ 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 \(\displaystyle{ 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ę \(\displaystyle{ 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ć \(\displaystyle{ 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 \(\displaystyle{ 27}\).

Teraz zbieramy dane o kolorowaniach stałych dla poszczególnych izometrii. Przyda nam się w tym celu pogrupowanie elementów \(\displaystyle{ S_4}\) w klasy sprzężoności:
  • identyczność (\(\displaystyle{ 1}\) sztuka) \(\displaystyle{ \rightarrow}\) \(\displaystyle{ 27}\) kolorowań stałych.
  • obroty o \(\displaystyle{ \pm\pi/2}\) wokół osi łączących środki ścian (\(\displaystyle{ 6}\) sztuk) \(\displaystyle{ \rightarrow}\) po \(\displaystyle{ 9}\) kolorowań stałych, para naprzeciwległych ścian przechodzi w siebie, pozostałe muszą być jednobarwne.
  • obroty o \(\displaystyle{ \pi}\) wokół osi łączących środki przeciwległych ścian (\(\displaystyle{ 3}\) sztuki) \(\displaystyle{ \rightarrow}\) po \(\displaystyle{ 27}\) kolorowania stałych, bo zachowują przeciwlegle ściany.
  • obroty o \(\displaystyle{ \pi}\) wokół osi łączących środki przeciwległych krawędzi (\(\displaystyle{ 6}\) sztuk) \(\displaystyle{ \rightarrow}\) po \(\displaystyle{ 9}\) kolorowania stałych, bo zachowują parę naprzeciwległych ścian, zaś pozostałe muszą być jednobarwne.
  • obroty wokół przekątnych sześcianu (o kat \(\displaystyle{ \frac{2\pi}{3}}\) patrząc wzdłuż osi) (\(\displaystyle{ 8}\) sztuk)\(\displaystyle{ \rightarrow}\) po \(\displaystyle{ 3}\) kolorowania stale, bo wszystkie ściany muszą być jednego koloru.
\(\displaystyle{ 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}\)
Ostatnio zmieniony 20 lis 2011, o 20:25 przez xiikzodz, łącznie zmieniany 3 razy.
Awatar użytkownika
max
Użytkownik
Użytkownik
Posty: 3306
Rejestracja: 10 gru 2005, o 17:48
Płeć: Mężczyzna
Lokalizacja: Lebendigentanz
Podziękował: 37 razy
Pomógł: 778 razy

Lemat Burnside'a

Post autor: max »

xiikzodz pisze:Lemat Burnside'a powiada:

Jesli grupa skonczona \(\displaystyle{ G}\) dziala na zbiorze \(\displaystyle{ X}\), to liczba orbit tego dzialania \(\displaystyle{ N}\) wyraza sie suma:

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

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

czyli zbioru punktow stalych elementu \(\displaystyle{ g}\).
(...)
To jeszcze jakiś dowód można podać:

Najpierw drobne przygotowania:

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

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

Teraz możemy przejść do dowodu lematu Burnside'a.
Niech \(\displaystyle{ \Omega_{1},\ldots, \Omega_{N}}\) będą rozłącznymi orbitami działania \(\displaystyle{ G}\) na \(\displaystyle{ X}\).
Zauważmy, że \(\displaystyle{ \forall_{x\in X, g\in G}\ g(x) = x \iff g\in \mbox{Stab}(x)}\) (z definicji stabilizatora w (i)) oraz
\(\displaystyle{ \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 \(\displaystyle{ i = 1, \ldots, N}\):
\(\displaystyle{ \sum_{g\in G} |\{x\in \Omega_{i} : g(x) = x| = \mbox{Stab}(x_{0})\cdot [G \ : \ \mbox{Stab}(x_{0})] = |G|}\), gdzie \(\displaystyle{ x_{0}}\) jest dowolnie ustalonym elementem \(\displaystyle{ \Omega_{i}}\).
Ponieważ \(\displaystyle{ \bigcup_{i=1}^{N}\Omega_{i} = X}\) to:
\(\displaystyle{ \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 \(\displaystyle{ g\in G}\):
\(\displaystyle{ 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:
\(\displaystyle{ \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|}\)
\(\displaystyle{ \blacksquare}\)
ODPOWIEDZ