Przeskocz do treści

Delta mi!

Loading

Teoria grup w kombinatoryce

Paweł Burzyński

o artykule ...

  • Publikacja w Delcie: sierpień 2016
  • Publikacja elektroniczna: 31 lipca 2016
  • Wersja do druku [application/pdf]: (307 KB)

Ten artykuł będzie poświęcony zliczaniu różnych kolorowań obiektów, które podlegają symetrii. Wyobraźmy sobie, że Kalina chciałaby pokolorować rogi kwadratu za pomocą m kolorów. Ile różnych figur może w ten sposób otrzymać?

Poniższy rysunek przedstawia wszystkie możliwe kolorowania dwoma kolorami, podzielone na zbiory kolorowań identycznych względem izometrii.

obrazek

Jak widać istnieje 16 kolorowań dwoma kolorami, ale tylko 6, gdy dopuścimy obracanie kwadratem i odbicia symetryczne. Aby obliczyć liczbę kolorowań większą liczbą kolorów, przyjrzyjmy się dokładnie izometriom naszego obiektu.
W przypadku kwadratu jest ich 8:

  • identyczność,
  • obroty o  ○ ○ ○ 90 ,180 ,270 ,
  • odbicia względem przekątnych, osi pionowej oraz osi poziomej.

Dodatkowo izometrie dowolnego obiektu można składać. Oznaczmy tę operację |○. Przykładowo: jeżeli odbijemy kwadrat względem osi pionowej, a następnie obrócimy go o 180○, otrzymamy odbicie względem osi poziomej. Zbiór izometrii wraz z operacją ○ ma poniższe podstawowe własności, dzięki którym tworzą one grupę, którą od teraz będziemy oznaczać przez |G

  • złożenie dowolnych dwóch izometrii również jest izometrią;
  • działanie ○ jest łączne, czyli dla dowolnych p,q,r ∈G mamy (p ○ q)○ r = p ○(q ○r) ;
  • istnieje element neutralny |e nazywany identycznością, taki że dla dowolnego p ∈ G zachodzi p | ○ e = e ○p = p ;
  • dla dowolnego p ∈G istnieje izometria odwrotna nazywana p −1, taka że p ○ p−1 = p−1○ p = e.

Zachęcam Czytelnika, aby samodzielnie uzasadnił powyższe własności grupy izometrii.

Jeżeli oznaczymy teraz zbiór wszystkich kolorowań kwadratu |m kolorami (dla pewnego ustalonego m ) przez A, będziemy mogli zdefiniować działanie grupy G na zbiór A. | Zauważmy, że dowolna symetria |g z G może działać na każdy element z A, | przekształcając go na pewien inny. Mówiąc formalnie, jest to funkcja spełniająca dwie własności:

  • (g1 ○g2)(a) = g1(g2(a)),
  • e(a) = a.

Aby lepiej zrozumieć działanie grupy izometrii na kolorowaniach obiektu, warto przyjrzeć się rysunkowi kolorowań kwadratu i zastanowić się, którymi izometriami trzeba działać na kolorowania z każdej grupy, aby otrzymać pozostałe.

Zanim przejdziemy do kluczowego twierdzenia, potrzebujemy jeszcze trzech nowych pojęć. Dla dowolnej izometrii g zbiorem jej punktów stałych będą wszystkie kolorowania |a, takie że |g(a) = a - będziemy ten zbiór oznaczać przez fix(g). Dla dowolnego kolorowania a zbiorem jego stabilizatorów będą wszystkie symetrie |g, takie że g(a) = a - ten zbiór będziemy oznaczać przez |stab(a). Ostatecznie, dla pewnego kolorowania a orbitą, do której ono należy, będzie zbiór wszystkich innych kolorowań, które można otrzymać z a działając pewną izometrią z |G. Ten zbiór będziemy nazywać orb(a). | Zauważmy teraz, że na rysunku wszystkich kolorowań kwadratu (poprzednia strona) zostały one podzielone właśnie na orbity. Każda orbita odpowiada jednemu sposobowi kolorowania obiektu, zatem naszym celem jest obliczenie ich liczby.

Niech a oraz |b będą dwoma kolorowaniami należącymi do tej samej orbity. Ponadto niech H oznacza zbiór wszystkich takich izometrii h, że |h○ a = b ; zauważmy również, że |h−1(b) = a. Wybierzmy dowolną izometrię |h ∈H . Składając ją lewostronnie ze wszystkimi izometriami ze zbioru |stab(a), otrzymamy | stab(a) różnych izometrii należących do |H. Zatem  H ⩾ stab(a) . Ponadto a można składać z odwrotnościami wszystkich izometrii z H, otrzymując | H izometrii należących do |stab(a). Z tego wynika, że  H ⩽ stab(a) , więc:

 H = stab(a) = stab(b) .

Jeżeli zadziałamy na kolorowanie |a wszystkimi izometriami z G, to każde z kolorowań ze zbioru |orb(a) otrzymamy dokładnie tyle samo razy w wyniku działania grupy. Można zatem wywnioskować bardzo ważny lemat:

∀ a>A stab(a) ⋅ orb(a) = G .

Teraz jesteśmy gotowi, aby wyprowadzić kluczowy wzór. Oznaczając zbiór wszystkich orbit poprzez |Ω, otrzymujemy:

 Ω = Q ----1--- = Q s tab(a)- = Pg>-G- fix(g) . a> A orb(a) a> A G G

Ostatnia równość wynika z faktu, że zarówno Pa> As tab(a) , jak i Pg> G fix(g) są równe liczbie par |(g,a), takich że g(a) = a. Wyprowadzona powyżej tożsamość nazywana jest lematem Burnside'a. Zbiór A jest niejednokrotnie ogromny, przez co nie ma możliwości badania wszystkich orbit. Dzięki tej równości wystarczy sklasyfikować izometrie z grupy |G, których jest stosunkowo niewiele. Jedyną trudnością, jaka pozostała, jest obliczenie dla każdej izometrii, ile ma ona punktów stałych. Aby to zrobić, musimy spojrzeć, które spośród rogów kwadratu dana izometria przekształca na które. W ten sposób rozbijemy je na cykle, a każdy z nich będzie musiał być w tym samym kolorze. Jeżeli izometria ma k | cykli, to ma ona mk punktów stałych, ponieważ każdy z nich kolorujemy jednym kolorem.

Dla ułatwienia ponumerujmy rogi kwadratu od 1 do 4 tak, jak numeruje się ćwiartki układu współrzędnych. Poniższa tabela przedstawia, jakie cykle powstaną dla wszystkich izometrii kwadratu. Zachęcam do jej dokładnego przeanalizowania.

obrazek

Podsumowując dane z tabeli i wstawiając je do otrzymanego wzoru, możemy wyprowadzić wzór na liczbę różnych kolorowań kwadratu |m kolorami:

m4 + 2m3 + 3m2 + 2m --------------------. 8

Spróbujmy teraz zmierzyć się z trudniejszym problemem. Wyobraźmy sobie, że Kalina chciałaby pokolorować wszystkie ściany sześciennej kostki, mając do dyspozycji kredki w |m kolorach. Ile różnych kostek mogłaby w ten sposób otrzymać? Tym razem nie będziemy wypisywać wszystkich izometrii sześcianu, musimy to zrobić sprytniej. Zacznijmy od tego, że obracając sześcian, możemy go postawić na dowolnej ze ścian, a następnie obrócić na cztery sposoby, zatem mamy 6⋅4 = 24 izometrie. Spróbujmy je teraz sklasyfikować.

  • Identyczność. Każda ściana przechodzi sama na siebie, tworząc osobny cykl, zatem ma ona m6 punktów stałych.
  • Obrót o |90○ lub 270 ○ względem osi przechodzącej przez środki przeciwległych ścian. Jest 3⋅2 = 6 takich izometrii. Dla każdej z nich dwie ściany, przez które przechodzi oś symetrii, przechodzą same na siebie, natomiast pozostałe ściany tworzą jeden cykl, zatem mamy m3 punktów stałych.
  • Obrót o 180○ względem osi przechodzącej przez środki przeciwległych ścian. Są trzy takie izometrie. Cykle zachowują się podobnie jak w poprzednim przypadku, ale cykl długości 4 rozbija się na 2 cykle długości 2. Mamy zatem m4 punktów stałych.
  • Obrót o 120○ lub o 240○ względem osi przechodzącej przez parę przeciwległych wierzchołków. Mamy 4 ⋅2 = 8 takich izometrii. Każda z nich tworzy dwa cykle długości |3 przy obu wierzchołkach, tworząc m2 punktów stałych.
  • Obrót o |180 ○ względem osi przechodzącej przez środki przeciwległych krawędzi. Jest |6 takich izometrii. W każdej z nich 2 pary ścian połączone krawędziami, przez które przechodzi oś, oraz pozostałe |2 ściany, przechodzą na siebie nawzajem. Mamy trzy cykle długości 2, więc jest |m3 punktów stałych.

Zauważmy, że rozpatrzyliśmy już wszystkie 24 izometrie. Po podstawieniu otrzymanych danych do wzoru otrzymujemy wzór na liczbę nieizometrycznych kolorowań ścian sześcianu |m kolorami:

m6 +-3m4 +-12m3 +-8m2----- 24 .

Po przeczytaniu tego artykułu warto spróbować własnych sił i ustalić, na ile sposobów Kalina mogłaby pokolorować czworościan, a na ile ośmiościan foremny za pomocą m kolorów.