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 » 19 lis 2008, o 05:26

Lemat Burnside'a powiada:

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

[latex]N=\frac{1}{|G|}\sum_{g\in G}S(g)[/latex]

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

czyli zbioru punktów stałych elementu [latex]g[/latex].

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 [latex]S(g)[/latex] jest dużo prostsze od bezpośredniego wyznaczania [latex]N[/latex]. 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 [latex]11[/latex]-kata foremnego tak, by były [latex]2[/latex] niebieskie, [latex]2[/latex] zielone i [latex]7[/latex] czerwonych wierzchołków?


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

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

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

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 [latex]\binom{10}{1}\binom{9}{3}= 840[/latex] sposobów (wybieramy czerwony wierzchołek, a potem z reszty 3 białe).

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

Możemy teraz przystąpić do zliczania orbit: [latex]N[/latex].

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

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

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 [latex]4[/latex], 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ę [latex]S_4[/latex] 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ć [latex]S_4\times C_2[/latex].

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

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

[list]
  • [*] identyczność ([latex]1[/latex] sztuka) [latex]\rightarrow[/latex] [latex]27[/latex] kolorowań stałych.

  • [*] obroty o [latex]\pm\pi/2[/latex] wokół osi łączących środki ścian ([latex]6[/latex] sztuk) [latex]\rightarrow[/latex] po [latex]9[/latex] kolorowań stałych, para naprzeciwległych ścian przechodzi w siebie, pozostałe muszą być jednobarwne.

  • [*] obroty o [latex]\pi[/latex] wokół osi łączących środki przeciwległych ścian ([latex]3[/latex] sztuki) [latex]\rightarrow[/latex] po [latex]27[/latex] kolorowania stałych, bo zachowują przeciwlegle ściany.

  • [*] obroty o [latex]\pi[/latex] wokół osi łączących środki przeciwległych krawędzi ([latex]6[/latex] sztuk) [latex]\rightarrow[/latex] po [latex]9[/latex] kolorowania stałych, bo zachowują parę naprzeciwległych ścian, zaś pozostałe muszą być jednobarwne.

  • [*] obroty wokół przekątnych sześcianu (o kat [latex]\frac{2\pi}{3}[/latex] patrząc wzdłuż osi) ([latex]8[/latex] sztuk)[latex]\rightarrow[/latex] po [latex]3[/latex] kolorowania stale, bo wszystkie ściany muszą być jednego koloru.
  • [/list]


    [latex]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[/latex]
    Ostatnio zmieniony 20 lis 2011, o 20:25 przez xiikzodz, łącznie zmieniany 3 razy.

    Awatar użytkownika
    max
    Gość Specjalny
    Gość Specjalny
    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 » 19 lis 2008, o 19:37

    [quote="xiikzodz"]Lemat Burnside'a powiada:

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

    [latex]N=\frac{1}{|G|}\sum_{g\in G}S(g)[/latex]

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

    czyli zbioru punktow stalych elementu [latex]g[/latex].
    (...)[/quote]


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

    Najpierw drobne przygotowania:

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

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

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

    ODPOWIEDZ