Lemat Burnside’a

Wstęp

Praca dotyczy problematyki teorii zliczania, a mianowicie zagadnień związanych z obliczaniem liczby t(G) orbit grupy G w zbiorze N przy danej liczbie charakterów permutacji należących do grupy (G,N).

Wyznaczenie wspomnianej już liczby czyli liczby orbit danej grupy umożliwia lemat Burnside’a. Ma on zastosowanie w różnorodnych dziedzinach wiedzy. Wykorzystywany jest w przypadku kolorowania wielokątów regularnych oraz wielokątów skierowanych, a w rezultacie ma zastosowanie w teorii liczb, w tym w małym twierdzeniu Fermata i twierdzeniu Wilsona ( patrz [5]). Lemat ten ma także zastosowanie w chemii ( klasy równoważności ubarwienia wierzchołków na wykresie dwunastościanu są wymienione jako działania swojej grupy automorficznej patrz [3]), w zliczaniu grafów, a nawet, co bardzo zadziwia, w muzyce ( patrz [1]). Należy jednak zaznaczyć, że sam lemat Burnside’a ma charakter teoretyczny i w praktyce stosowane są takie jego rozwinięcia jak np. twierdzenie Polyi.

W rozdziale pierwszym wyjaśnione są pojęcia: charakter permutacji, permutacja podobna, permutacja sprzężona, a następnie są one poparte przykładami. Rozdział pierwszy zawiera również twierdzenie Lagrange’a, które wykorzystane jest w dowodzie głównego twierdzenia, czyli lematu Burnside’a.

Rozdział drugi zawiera ogólny schemat zastosowań lematu Burnside’a wraz z przykładami.

Materiał przedstawiony w pracy został zaczerpnięty głównie z monografii [2] i [6].

Lemat Burnside'a


Definicja1.1
Charakterem (g) permutacji g S(N) zbioru N nazywamy liczbę punktów stałych permutacji g w zbiorze N, tzn. liczbę cykli długości 1 w rozkładzie g na cykle.

Przykład 1.2
Jeśli g=(1)(234)(5) S5 , to (g)=2.

Definicja1.3
Niech (G,N) będzie grupą permutacji. Określamy relację r N N następująco:
. Klasy abstrakcji relacji r wyznaczającej podział zbioru N nazywamy orbitami grupy G. Każda orbita ma postać aG={ag  g G} dla pewnego a N.

Definicja1.4
Grupę wszystkich permutacji zbioru N nazywamy grupą symetryczną zbioru N i oznaczamy przez S(N). Jeżeli moc zbioru N jest równa n, to oznaczamy ją również krótko przez Sn i nazywamy grupą symetryczną stopnia n.
Pod nazwą grupa permutacji G będziemy rozumieć parę (G,N) złożoną z grupy permutacji G oraz zbioru N, na elementach którego te permutacje działają.

Definicja1.5
Podgrupę Ga={g G ag =a} grupy permutacji (G,N) nazywamy stabilizatorem elementu a w grupie G.

Definicja1.6
Graf, czyli graf skierowany Φ =(V(Φ), E(Φ)) składa się ze zbioru V(Φ), którego elementy nazywamy wierzchołkami, oraz z pewnej relacji binarnej E(Φ) V(Φ) V(Φ).
Element (a,b) E(Φ) nazywamy krawędzią skierowaną, lub krótko łukiem, o początku a i końcu b.

Definicja1.7
Dwie permutacje g1, g2 tego samego zbioru N nazywamy podobnymi, jeżeli w ich rozkładach na cykle występuje tyle samo cykli tej samej długości.

Przykład1.8
Permutacje g1=(1)(2)(345)(678910) i g2=(1)(237910)(4)(568) są podobne. Obie mają po dwa cykle długości jeden i po jednym cyklu długości trzy i pięć.

Definicja 1.9
Mówimy, że permutacja g1 Sn jest sprzężona z permutacją g2 Sn względem pewnej grupy permutacji G Sn ( krótko: sprzężona względem G), jeżeli istnieje element g grupy G taki, że g-1g1g=g2.

Zauważmy, że permutacje podobne, a więc i permutacje sprzężone, mają charaktery równe.

Twierdzenie 1.10
Dwie permutacje g , g′ Sn są sprzężone w Sn dokładnie wtedy, gdy są podobne.

Dowód.
Jeżeli permutacje g i g′ mają rozkłady na cykle
g=(a1a2 ... ak)(b1b2 ... bx) ... ( ... )
g’=(a’1a’2 ... a’k)(b’1b’2 ... b’x) ... ( ... )

i są podobne, to permutacja


a1a2 ... akb1b2 ... bx ...
= Sn
a’1a’2 ... a’kb’1b’2 ... b’x ...




spełnia g’= 1g. Wynika to natychmiast z następującego stwierdzenia:

Stwierdzenie 1.11
Jeżeli jest dany rozkład na cykle permutacji gSn, to dla Sn rozkład na cykle permutacji g’=1g otrzymujemy z rozkładu permutacji g zastępując każdą z występujących w nim liczb przez jej obraz przy .

Wynika z niego też, że i na odwrót, permutacje sprzężone są podobne.

Znając charaktery wszystkich permutacji należących do pewnej grupy (G,N) łatwo jest wyznaczyć liczbę t(G) orbit grupy G w zbiorze N. Twierdzenie, które umożliwia wyznaczenie tej liczby, stanowi podstawę całej teorii zliczania i jest zwane w literaturze jako lemat Burnside’a.


Lemat Burnside’a

Liczba t(G) 1-orbit grupy permutacji G równa jest średniej arytmetycznej charakterów elementów grupy G, tzn.
.

Dowód.
Graf Φ={(a,h)  h Ga}
1 2 3 4 5 6 7 8 9 10 11


Rys. 1







e g g² g³ g4 g5

Rozpatrujemy graf Φ, którego zbiór wierzchołków jest sumą dwóch zbiorów rozłącznych, a mianowicie N i G: V(Φ)=NG. Łuki E(Φ) tego grafu łączą tylko wierzchołki należące do różnych podzbiorów, łuk biegnie od wierzchołka a N do wierzchołka g G dokładnie wtedy, gdy a jest punktem stałym permutacji g, tzn. E(Φ)={(a, g)  a N, g Ga}. Obliczymy teraz liczbę łuków |E(Φ)| na dwa sposoby.
Najpierw ustalamy g G. Wtedy {a (a, g) E(Φ)} jest zbiorem punktów stałych permutacji g, ma zatem (g) elementów. Jest więc (g) łuków dochodzących do wierzchołka g, tzn.
(2) .
Z kolei ustalamy a N. Wtedy
Ga={g G (a,b) E(Φ)}.
Jest więc |Ga| łuków wychodzących z punktu a N,
tzn. (3) |E(Φ)|= .

Twierdzenie 1.12 ( twierdzenie Lagrange'a).
Rząd każdej podgrupy H grupy skończonej G jest dzielnikiem rzędu G.

Twierdzenie 1.13
Niech (G,N) będzie grupą permutacji i niech B będzie orbitą grupy G. Wtedy moc tej orbity jest równa indeksowi [G : Ga] stabilizatora Ga dowolnego elementu a B.

Uwaga 1.14
W przypadku z twierdzenia 1.3 twierdzenie Lagrange'a można też zapisać w postaci |G|=| aG| |Ga| ( a N).

Jeżeli a i b należą do tej samej orbity grupy G (tzn. aG = bG , gdyż każda orbita ma postać aG={ag  g G} dla pewnego a N), to z twierdzenia Lagrange'a wynika, że , tzn.
(4)
Ponieważ jest t(G) orbit aG, więc otrzymujemy stąd natychmiast, że
(5) |E(Φ)|= .
Zbierając razem otrzymane równości stwierdzamy, że
,
a stąd dzieląc stronami przez |G| otrzymujemy :
,
co dowodzi lematu.


Przykład 1.15
Mamy daną grupę cykliczną G= , gdzie g=(1,2,3,4,5,6)(7,8,9)(10,11) zawiera sześć elementów e,g,g²,g³,g4,g5.
Na rysunku ( Rys. 1) jest pokazany graf Φ grupy G, który występował w dowodzie lematu Burnside'a. Obliczymy teraz liczbę orbit grupy G.



Zastosowania


Lemat Burnside'a w teorii zliczania z reguły stosujemy następująco. Najpierw wprowadzamy grupę permutacji (G,N) związaną z rozważanym zagadnieniem i ją badamy. Następnie za pomocą zbioru N konstruujemy nowy zbiór i rozszerzamy działanie grupy G na zbiór . Powstaje w ten sposób pewna nowa grupa permutacji (G,N), tzw. grupa permutacji indukowana.

Definicja 2.1
Określamy działanie permutacji ,w zbiorze (inaczej, permutacja g indukuje permutacje zbioru ) za pomocą współrzędnych dla i .

Wreszcie do tej grupy indukowanej stosujemy nasz lemat, by znaleźć liczbę t(G) orbit grupy G w zbiorze N (grupę G obieramy w ten sposób, by liczba t(G) była rozwiązaniem wyjściowego zagadnienia). Ten schemat postępowania bywa szczególnie efektywny, gdy charaktery permutacji indukowanych można wyznaczyć ze wskaźnika cyklowego grupy (G,N) bez potrzeby wykorzystywania jawnej postaci permutacji.

Przykłady:
Przykład 2.2
Niech G będzie grupą cykliczną rzędu 6 i stopnia 11 z przykładu 1.3. Grupa G jest przechodnia i ma w zbiorze N={1,2,...,11} trzy orbity. Pokażemy na tym przykładzie zastosowanie lematu Burnside'a, nie wiążąc jednak tego z żadnym konkretnym "praktycznym" zagadnieniem. Przyjmijmy, że w pewnym zagadnieniu kombinatorycznym mamy wyznaczyć liczbę 2-orbit przeciwzwrotnych grupy permutacji (G,N). W tym celu najpierw rozważmy nowy zbiór złożony ze 110 par uporządkowanych różnych elementów zbioru N. Rozpatrując działanie grupy G w zbiorze otrzymujemy grupę indukowaną , dla której liczba orbit jest równa liczbie 2-orbit przeciwzwrotnych grupy (G,N)( tu jest permutacją zbioru indukowaną przez ). Dla obliczenia charakterów permutacji indukowanych zauważmy, że jest dokładnie wtedy punktem stałym permutacji ( tzn. ), gdy a i b są punktami stałymi permutacji g ( tzn. ). Wobec tego mamy .
Zatem t(G)=
Grupa (G,N) ma więc 20 2-orbit przeciwzwrotnych. Dla wyznaczenia tej liczby nie musieliśmy znać poszczególnych punktów tych 2-orbit. Jest to sytuacja typowa w teorii zliczania.

Przykład 2.3
Obieramy n symboli i oznaczamy każdy bok pewnego kwadratu jednym z tych symboli. Jest oczywiście możliwych takich oznaczeń. Przy tym pewne z nich przechodzą na inne przy obrotach kwadratu. Stawiamy pytanie: ile jest istotnie różnych( tzn. nie różniących się o obrót kwadratu) możliwości takiego oznaczenia boków kwadratu?
Podamy teraz inne sformułowanie tego zadania, które stanie się przez to może bardziej interesujące. Obie przekątne kwadratu dzielą go na cztery trójkąty. Mają one być pomalowane za pomocą n kolorów. Każdy kwadrat pomalowany w ten sposób nazwiemy n -kolorową kwadratową kostką domina. Zadanie: znaleźć wszystkie istotnie różne kostki domina! Dla n=2 wszystkie istotnie różne kostki domina są podane na rysunku 2.

Rys. 2


W przypadku n =3 są 24 istotnie różne kostki domina ( patrz rysunek 3) i znalezienie ich wymaga już pewnej wprawy.

Rys. 3


Oznaczenie x
y
z
gdzie x, y, z oznaczają trzy różne kolory.

Dla n =4, gdyby chciało się podać jawnie wszystkie kostki domina, rozwiązanie tego zadania byłoby bardzo pracochłonne.
Aby otrzymać wzór na liczbę istotnie różnych n -kolorowych kostek domina postępujemy następująco. Rozważamy grupę C4 ( czyli grupę złożoną ze wszystkich potęg permutacji g=(0123)) obrotów kwadratu, którą rozpatrujemy jako grupę permutacji zbioru {1,2,3,4} boków kwadratu (albo też trójkątów). Następnie rozważamy zbiór wszystkich możliwych kolorowań kwadratu i indukowaną grupę permutacji zbioru (jeżeli bok kwadratu ma kolor , to element działa na kolorowaniu za pomocą wzoru ; wtedy również określa pewne kolorowanie). Zauważmy, że liczba orbit grupy jest równa szukanej liczbie istotnie różnych n -kolorowych kostek domina. Jak obliczyć ? Niech . Wówczas nie zmienia pewnego kolorowania f boków kwadratu dokładnie wtedy, gdy , co jest równoważne z (i=1,2,3,4), tzn. boki, które należą do jednego cyklu permutacji g, muszą być pomalowane na ten sam kolor. Mamy więc
,
gdzie c(g) jest liczbą wszystkich cykli w rozkładzie permutacji g na cykle.

Definicja 2.4
Indeksem cyklowym grupy permutacji stopnia n nazwiemy wielomian



tzn. średnią arytmetyczną typów wszystkich permutacji należących do grupy G.

Dla grupy łatwo jest obliczyć wskaźnik cyklowy:


Wynika stąd, że


W szczególności mamy .
Możemy teraz zrobić ważną uwagę: poszukiwaną liczbę orbit grupy można otrzymać ze wskaźnika cyklowego grupy C4 podstawiając na miejsce każdej zmiennej liczbę n .

Przykład 2.5
Na szachownicy o polach należy rozmieścić n wież w taki sposób, by się wzajemnie nie szachowały, tzn. w każdym wierszu poziomym i w każdym wierszu pionowym może się znajdować co najwyżej jedna wieża. Na ile istotnie różnych sposobów jest to możliwe? Przy tym dwa rozmieszczenia wież uznamy za równoważne( tzn. różniące się nieistotnie), jeżeli z jednego można otrzymać drugie za pomocą pewnej izometrii szachownicy. Rozwiążemy to zadanie dla n=4. Grupą izometrii szachownicy jest grupa dwuścianu , którą rozważymy jako grupę permutacji zbioru K szesnastu pól szachownicy. Łatwo się przekonać, że mamy łącznie sposoby rozmieszczania czterech wież tak, by wzajemnie się nie szachowały. Zbiór wszystkich możliwych rozmieszczeń czterech wież oznaczamy przez ; działanie grupy można rozszerzyć na zbiór , ponieważ każda izometria szachownicy określa odwzorowanie danego na niej rozmieszczenia wież. Można teraz do grupy indukowanej zastosować lemat Burnside’a. W tym celu wyznaczamy charaktery permutacji indukowanych.

Definicja 2.6
Grupę izometrii n- kąta foremnego nazywamy grupą dwuścianu i oznaczamy przez .

Twierdzenie 2.7
Rząd grupy dwuścianu jest równy 2n. Składa się on z n obrotów o kąty oraz n symetrii osiowych.
(Przy n nieparzystym osie tych symetrii zawierają wierzchołek i środek przeciwległego boku. Przy n parzystym połowa tych osi symetrii przechodzi przez środki przeciwległych boków, a pozostała połowa- przez przeciwległe wierzchołki).

Mam = , gdzie
jest permutacją tożsamościową;
są symetriami względem prostych łączących środki przeciwległych boków;
są symetriami względem przekątnych;
jest obrotem o .
Oczywiście . Ponieważ jest symetrią względem prostej łączącej środki przeciwległych boków, więc nie może zachowywać żadnego rozmieszczenia wież. W przeciwnym razie dwie wieże musiałyby się znaleźć w tym samym wierszu poziomym ( lub pionowym). Stąd . Następnie mamy ; jeżeli bowiem zachowuje pewne rozmieszczenie wież, to żadna wieża nie może stać na polu narożnym ( są dwie takie możliwości), to położenie pozostałych trzech wież będzie przez to jednoznacznie wyznaczone. Dla (obrót o )wyznaczamy podobnie, że . Trudniej jest znaleźć . Ponieważ jest symetrią względem przekątnej, musimy więc rozważyć dwa przypadki. Pierwszy: w wierszu pierwszym znajduje się wieża na polu należącym do osi symetrii. Wtedy dla rozmieszczenia pozostałych trzech wież mamy do dyspozycji szachownicę ( daje to cztery możliwości). Drugi: w wierszu pierwszym znajduje się wieża na polu nienależącym do osi symetrii ( są trzy takie możliwości), wtedy położenie pewnej innej wieży jest wyznaczone jednoznacznie i pozostaje szachownica dla rozmieszczenia pozostałych dwóch wież. Wobec tego mam . Ponieważ elementy sprzężone (mianowicie , podobnie jak oraz ) mają charaktery równe, więc po zastosowaniu lematu Burnside’a otrzymujemy

.

Istnieje więc siedem rozmieszczeń parami nierównoważnych; są one podane na rysunku 4. Wieże są oznaczone trójkątami.

Rys. 4

Uwaga 2.8
Wymienione wyżej elementy są sprzężone w grupie , ponieważ , podobnie jak oraz są sprzężone już w grupie ( zauważmy, że elementy oraz są podobne, jednak nie są w grupie ze sobą sprzężone, ponieważ ich charaktery indukowane i są różne).

Przykład 2.9 ( Naszyjniki)
Problem: dysponujemy zapasem białych i czarnych paciorków, które nawlekamy na sznurek i łączymy go w pętle. Ile możemy nawlec „istotnie różnych” naszyjników o n paciorkach? Dokładniej malujemy wierzchołki n -kąta foremnego na biało i czarno. Można to oczywiście zrobić na sposobów. Dwa pokolorowania uznamy za różne, jeżeli nie istnieje przekształcenie z grupy symetrii n -kąta foremnego, które jedno z tych pokolorowań przekształca na drugie.
Stawiamy pytanie: ile różnych naszyjników można utworzyć z pięciu korali mając do dyspozycji korale dwóch kolorów?

Traktując naszyjnik jako cykl długości pięć, mamy tu grupę przekształceń złożoną z identyczności i z czterech obrotów o jedno, dwa, trzy i cztery „oczka”, a jeśli dopuszczamy operacje trójwymiarowe (podniesienie naszyjnika ze stołu), to dochodzi jeszcze pięć symetrii względem osi łączących wierzchołki ze środkami przeciwległych krawędzi. Jeśli oznaczyć wierzchołki cyklu kolejno od 1 do 5, to są to następujące permutacje: (1)(2)(3)(4)(5), (12345), (13524), (14253), (15432) oraz (1)(25)(34), (2)(13)(45) itd. W przypadku płaskim jest jedna permutacja o pięciu cyklach i cztery o jednym cyklu, co daje w efekcie:
.
W przypadku trójwymiarowym jest jedna permutacja o pięciu cyklach, a mianowicie identyczność, i ma ona wobec tego w zbiorze pokolorowań punktów stałych. Ponadto jest pięć permutacji o trzech cyklach - odbicia – i każda z nich ma punktów stałych, oraz są cztery cykle długości pięć – nieidentycznościowe obroty – każdy z dwoma punktami stałymi. Z lematu Burnside’a wynika, że wszystkich orbit jest
.
Następujące wyniki należy interpretować w ten sposób, że dodatkowe symetrie nie utożsamiają żadnej pary wśród ośmiu konfiguracji.

Gdyby mieć koraliki w trzech, a nie w dwóch kolorach, to odpowiednie liczby naszyjników wyniosłyby:


i
.
Zatem w tym przypadku dodatkowe symetrie powodują utożsamienie niektórych naszyjników, których nie dało się utożsamić tylko za pomocą obrotów.
Łatwo jest narysować wszystkie takie naszyjniki dla małych n. Dla n=5, wszystkie 8 różnych naszyjników pokazano na rysunku piątym.

Rys. 5

Indeks oznaczeń


Wprowadzam następujące oznaczenia:
(g)- charakter permutacji g (strona 5 definicja 1.1)
aG - orbita grupy G zawierająca element a (strona 5 definicja 1.3)
t(G)- liczba orbit grupy (G, N)
Sn , S(N)-grupa symetryczna zbioru N o n elementach (strona 5 definicja 1.4)
(G,N)- grupa permutacji zbioru N (strona 5 definicja 1.4)
Ga - stabilizator elementu a w grupie G (strona 5 definicja 1.5)
V(Φ)- wierzchołki grafu Φ (strona 5 definicja 1.6)
E(Φ)-łuki grafu Φ ( strona 5 definicja 1.6)
|E(Φ)|-liczba łuków grafu Φ
-grupa dwuścianu ( strona 12 definicja 2.6)