2208634440

Wykład 7 13 listopada 2012

1 Lemat Burnside’a

Twierdzenie 1.1 (Lemat Burnside’a) Niech G będzie grupa skończoną działającą na zbiorze skończonym X. Wówczas liczba N orbit zbioru X ze względu na G wynosi

W dowodzie lematu Bumside’a korzystamy z Bardzo Ważnego Twierdzenia udowodnionego podczas wykładu poprzedniego. Dla wygody przypominam więc to twierdzenie (w postaci, którą nazwaliśmy wnioskiem).

Wniosek 1.2 Jeśli skończona grupa G działa na zbiorze X, wówczas dla każdego

x€ X

(1)

\G\ = \G_X\ ■ |Orb x\

Dowód Lematu Burnside⁵a przeprowadzimy metodą, która w kombina-toryce jest znana pod nazwą metody podwójnego zliczania. Ta metoda polega na oczywistej zasadzie, że jeśli liczymy liczność jakiegoś zbioru na dwa sposoby to wynik za każdym razem musi być ten sam (oczywiście zakładamy, że obie metody są poprawne).

Policzymy liczbę elementów zbioru

S = {(»,<?) 6lxG: g{ x) = a?)

Utwórzmy zero-jedynkową macierz M = (m^_x)_g£c^£X zdefiniowaną wzorem

O takiej macierzy mówimy, że ma wiersze indeksowane elementami zbioru G, zaś kolumny indeksowane elementami zbioru X.

liczba elementów zbioru S jest oczywiście równa liczbie jedynek w macierzy M. Liczbę tę można obliczyć na dwa sposoby.

1