Matematyka dyskretna 2/Wykład 5: Zastosowania teorii grup w zliczaniu

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Kolorowanie zbioru to funkcja



gdzie jest zbiorem kolorów.

Poly pieciokat.swf

Przykład

Rozważmy kolorowania naszyjnika złożonego z pięciu identycznych koralików . Koraliki te mają takie same kształty i nie można ich rozróżnić. Możemy zatem zauważyć, że z jednego kolorowania da się utworzyć inne kolorowanie, nieodróżnialne od pierwszego, np. przez cykliczną zmianę numeracji koralików: jest nieodróżnialne od kolorowania . Przekształcenie indeksów jest równoważne z obrotem o .

W ten sposób dostajemy kolorowań naszego naszyjnika. Ale, naszyjnik można też odwracać w rękach, lub - co na jedno wychodzi - spojrzeć na niego z drugiej strony. Mamy więc dodatkowe kolorowań naszego naszyjnika.

Zauważmy, ze w istocie każde z kolorowań możemy otrzymać z innego poprzez przekształcenie naszyjnika (pięciokąta) przez jakąś symetrię. Zbiór zmian ułożeń naszyjnika (permutacje jego koralików) wraz ze składaniem tych zmian (permutacji) tworzy więc grupę (w tym przypadku znaną nam już grupę dihedralną symetrii pięciokąta. W wykładzie tym poznamy metody zliczania tych kolorowań, które są odróżnialne.

G-zbiór to para , gdzie

  • jest zbiorem skończonym,
  • jest grupą permutacji zbioru , tzn. jest zamkniętym na składanie

zbiorem permutacji zbioru .

Czasem, dla G-zbioru mówimy, ze grupa działa na zbiorze .

Przekształcenia odpowiadające permutacjom

Przykład

Rozważmy kwadrat o wierzchołkach oraz permutacje jego wierzchołków powstałe przez: odbicia względem przekątnych i obrót o , tak jak zostało to pokazane na rysunku.

Każde przedstawione przekształcenie geometryczne wyznacza jednoznacznie permutację zbioru indeksów wierzchołków kwadratu . Tak więc zbiór permutacji odpowiadających przekształceniom to . Przekształcenia można składać. Na przykład tworzy obrót o stopni, a więc . Para tworzy grupę, więc jest przykładem G-zbioru, który jest opisany przez poniższe tabelki:



Innymi słowy, grupa permutacji działa na zbiorze .

Orbita elementu w G-zbiorze to zbiór tych elementów zbioru , które są postaci dla pewnego , tzn.



Stabilizator elementu w G-zbiorze to zbiór tych permutacji z , które nie ruszają z miejsca, tzn.



Ponadto zbiór permutacji przeprowadzających w oznaczamy przez



Przykład

Dla grupy permutacji kwadratu z rysunku, orbita oraz stabilizator elementu mają postać



Mnożąc liczności obu tych zbiorów otrzymujemy liczbę elementów grupy , czyli innymi słowy

Jako ćwiczenie 3 pozostawiamy dowód następującej obserwacji.

Obserwacja 5.1

Dla G-zbioru oraz zachodzi



Twierdzenie 5.2

Dla G-zbioru oraz zachodzi



Dowód

Przy ustalonym policzmy, na dwa różne sposoby, pary w zbiorze



Dowolna permutacja wyznacza jednoznacznie element , tak więc Pogrupowanie par w zbiory tak, by



daje podział



Zbiór składa się z elementów, które można uzyskać jako za pomocą jakiejkolwiek permutacji , a zatem jest to orbita elementu :



Z kolei zaś jest zbiorem takich par , że . Permutacja jednoznacznie wyznacza element , tak więc jest równoliczny z



Tym samym Obserwacja 5.1 daje, że dla dowolnego . W konsekwencji .

End of proof.gif

Wniosek 5.3

W G-zbiorze wszystkie orbity mają tę samą liczność, tzn.



Zbiór punktów stałych permutacji to



Twierdzenie 5.4

Dla G-zbioru oraz funkcji stałej na każdej orbicie zachodzi



gdzie jest zbiorem reprezentantów orbit, tzn. dla dowolnego .

Dowód

Policzymy, na dwa różne sposoby, sumę



gdzie . Pogrupowanie par w zbiory , zdefiniowane przez



daje podział



Oczywiście , więc , czyli zbiór użytych w tym podziale indeksów wyczerpuje całe . Ponadto, z samej definicji , otrzymujemy . A zatem



gdzie jest dowolnie wybranym elementem zbioru . Niech teraz będzie zbiorem reprezentantów rodziny orbit, tzn. są parami rozłączne i . Ponieważ funkcja jest stała na orbitach, to



Równoliczność orbit uzyskana we Wniosku 5.3 wraz z Twierdzeniem 5.2 daje więc



Z drugiej strony, pogrupowanie par w zbiory zadane przez



daje podział



Każdy zbiór postaci jest bijektywny ze zbiorem punktów stałych permutacji



A zatem



co daje ostatecznie



End of proof.gif

Wniosek 5.5

Liczba orbit w G-zbiorze wynosi



Permutacje na zbiorze kolorowań. Niech będzie G-zbiorem, a zbiorem kolorowań zbioru . Każda permutacja wyznacza permutację kolorowań ze zbioru poprzez



Obserwacja 5.6

Niech będzie G-zbiorem, a zbiorem kolorowań zbioru . Dla zachodzi:

  • Para tworzy grupę, gdzie jest składaniem permutacji.
  • Funkcja jest izomorfizmem grup oraz .
  • .
  • jest G-zbiorem.

Izomorficzne kolorowania. Kolorowania i zbioru są izomorficzne względem działania grupy na zbiorze , gdy istnieje permutacja taka, że , czyli



Przykład

Kolorowania z rysunku są izomorficzne względem działania grupy wszystkich zmian ustawień -elementowego naszyjnika.

Indeks permutacji to funkcja zmiennych



gdzie

  • to liczność zbioru ,
  • to liczba -elementowych cykli permutacji ,

dla .

Indeks grupy to funkcja zmiennych


Plik:Poly tetrahedron 2.svg
Obrót o czworościanu względem prostej przechodzącej przez wierzchołek oraz przez środek ściany

Plik:Poly tetrahedron 3.svg
Obrót o czworościanu względem prostej przechodzącej przez środki krawędzi oraz

Przykład

Niech będzie grupą wszystkich obrotów czworościanu foremnego (przedstawionego na rysunku) w -wymiarowej przestrzeni.

Obroty czworościanu mają więc następujące indeksy , w zależności od rozkładu na cykle:

  • - jedyny taki obrót z jednoelementowymi cyklami to oczywiście .
  • - obroty o względem prostej przechodzącej przez jeden z wierzchołków i środek przeciwległej ściany. W grupie jest ich . Przykładem permutacji o indeksie jest , która odpowiada przekształceniu przedstawionym na rysunku.
  • - obroty o względem osi przechodzącej przez środki przeciwległych krawędzi.

W sumie są takie obroty. Permutacją o indeksie jest na przykład i odpowiada ona przekształceniu przedstawionym na rysunku.

Indeks całej grupy obrotów czworościanu to zatem:




Twierdzenie 5.7

Liczba nieizomorficznych kolorowań zbioru za pomocą barw wynosi



gdzie jest grupą możliwych permutacji elementów .

Dowód

Niech będzie zbiorem wszystkich kolorowań barwami zbioru . Szukana liczba nieizomorficznych kolorowań jest równa liczbie orbit G-zbioru i, na mocy Wniosku 5.5 oraz Obserwacji 5.6, wynosi:



Pozostaje więc policzyć liczbę punktów stałych każdej z permutacji . Jeśli jest punktem stałym permutacji , a jest cyklem tej permutacji, to



A zatem wszystkie elementy tego cyklu są pokolorowane na ten sam kolor. Niech teraz permutacja rozkłada się na cykli. Ponieważ elementy każdego cyklu muszą być jednobarwne, a wszystkich możliwych do wykorzystania barw jest , to liczba możliwych kolorowań elementów wynosi . Z drugiej strony



gdzie jest liczbą cykli elementowych. Ale oczywiście , skąd . Liczba nieizomorficznych kolorowań jest więc równa



End of proof.gif

Plik:Poly tetrahedron 4.svg
Nieizomorficzne kolorowania wierzchołków czworościanu foremnego

Przykład

Niech będzie grupą wszystkich obrotów czworościanu foremnego (przedstawionego na rysunku) w -wymiarowej przestrzeni. Wiemy już, że indeks grupy wynosi



Aby zliczyć wszystkie, nieizomorficzne względem obrotów, kolorowania wierzchołków czworościanu na kolory wystarczy, wobec Twierdzenia 5.7, policzyć wartość



Faktycznie. Jedynymi kolorowaniami nieizomorficznymi względem obrotów są te, przedstawione na rysunku.

Wskaźnik kolorowania , dla zbioru kolorów to



gdzie to liczba elementów ze zbioru pokolorowanych przez na kolor .
Ponadto dla zbioru kolorowań definiuje się funkcję tworzącą postaci



Twierdzenie 5.8

Dla podziału zbioru mamy



gdzie jest zbiorem kolorowań stałych na zbiorach .

Dowód

Niech . Iloczyn



jest sumą jednomianów postaci . Aby przeanalizować te jednomiany zauważmy, że mnożąc po jednym składniku z każdego czynnika iloczynu, otrzymamy jednomian postaci . Wartość jest więc równa wszystkim możliwym iloczynom dającym . Porządkując składniki otrzymujemy, że jest liczbą wszystkich zestawów sum postaci



Każdy taki zestaw sum można utożsamić z kolorowaniem, które przyporządkowuje elementom z pierwszą barwę, elementom z kolejną barwę, itd... Otrzymujemy w ten sposób, że jest liczbą kolorowań stałych na każdym ze zbiorów . Kolorowania te używają razy pierwszej barwy, razy drugiej barwy, itd..., czyli jednomian jest składnikiem w sumie powstałej z iloczynu przez wymnożenie wszystkich czynników.

End of proof.gif

Twierdzenie 5.9 [G. Pólya 1935]

Niech a będzie zbiorem wszystkich nieizomorficznych, ze względu na działanie grupy na zbiorze , kolorowań zbioru za pomocą barw. Wtedy funkcja tworząca jest postaci



gdzie



Dowód

Zbiór jest zbiorem reprezentantów orbit G-zbioru , gdzie jest zbiorem wszystkich możliwych kolorowań zbioru . Podstawiając, w Twierdzeniu 5.4, za funkcję wskaźnik kolorowania otrzymujemy



Korzystając z definicji wskaźnika kolorowania dostajemy



Zbiór jest zbiorem kolorowań, przy których elementy z tego samego cyklu otrzymują tę samą barwę. A zatem, z Twierdzenia 5.8 wynika, że



gdzie jest rozmiarem -tego cyklu. Niech będzie liczbą cykli w o długości . Otrzymujemy więc



Obserwacja 5.6 daje więc teraz



End of proof.gif

Plik:Poly square 2.mp4
Przekształcenia geometryczne kwadratu

Przykład

Użyjemy opisanych twierdzeń do wyznaczenia liczby wszystkich nieizomorficznych pokolorowań wierzchołków kwadratu na dwa kolory. Rozważmy więc wszystkie osiem symetrii kwadratu, jak przedstawiono na animacji.


Grupa permutacji wyznaczona przez te symetrie ma następujących elementów:



Z podanego rozkładu na cykle dostajemy, że indeks grupy to



Aby znaleźć liczbę nieizomorficznych kolorowań takich, że wierzchołków jest pokolorowanych na biało , a pozostałe na czarno , wystarczy wyliczyć współczynnik przy w funkcji tworzącej postaci



Rysunek przedstawia wszystkie możliwe nieizomorficzne kolorowania.

Nieizomorficzne kolorowania wierzchołków kwadratu