Jeśli grupa skończona \(\displaystyle{ G}\) działa na zbiorze \(\displaystyle{ X}\), to liczba orbit tego działania \(\displaystyle{ N}\) wyraża się suma:
\(\displaystyle{ N=\frac{1}{|G|}\sum_{g\in G}S(g)}\)
gdzie \(\displaystyle{ S(g)}\) jest liczba elementów zbioru \(\displaystyle{ \{x\in X: g(x)=x\}}\),
czyli zbioru punktów stałych elementu \(\displaystyle{ g}\).
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 \(\displaystyle{ S(g)}\) jest dużo prostsze od bezpośredniego wyznaczania \(\displaystyle{ N}\). 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 \(\displaystyle{ 11}\)-kata foremnego tak, by były \(\displaystyle{ 2}\) niebieskie, \(\displaystyle{ 2}\) zielone i \(\displaystyle{ 7}\) czerwonych wierzchołków?
Rozwiązanie: Wszystkich możliwych kolorowań (bez uwzględniania obrotów) jest \(\displaystyle{ \binom{11}{2}\binom{9}{2}=1980}\). Na zbiorze \(\displaystyle{ X}\) tych wszystkich kolorowań, działa grupa cykliczna \(\displaystyle{ 11}\)-elementowa, \(\displaystyle{ C_{11}}\) obrotów o wielokrotności kata \(\displaystyle{ \frac{2\pi}{11}}\). Dla obrotu o kat \(\displaystyle{ 0}\), czyli o element neutralny, wszystkie kolorowania są punktami stałymi, zatem \(\displaystyle{ S(0)=1980}\). Pozostałe elementy grupy \(\displaystyle{ C_{11}}\) nie maja żadnych punktów stałych:
Każdy element rożny od \(\displaystyle{ 0}\) generuje cala grupę \(\displaystyle{ C_{11}}\), gdyby wiec jakiś miał punkt stały, to również obrót jednostkowy o kat \(\displaystyle{ \frac{2\pi}{11}}\) nie ruszałby tego kolorowania. Lecz wówczas wszystkie wierzchołki musiałyby być jednobarwne.
Zatem odpowiedzią na pytanie jest liczba: \(\displaystyle{ N=\frac{1}{|C_{11}|}\cdot S(0)=\frac{1}{11}\cdot 1980=180}\).
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 \(\displaystyle{ \binom{10}{1}\binom{9}{3}= 840}\) sposobów (wybieramy czerwony wierzchołek, a potem z reszty 3 białe).
Na zbiorze tych kolorowań, oznaczmy go \(\displaystyle{ X}\), działa grupa dihedralna 20-elementowa: \(\displaystyle{ D_{10}}\). Grupa ta składa się z 10 obrotów (w tym o kat 0, który oznaczamy symbolem \(\displaystyle{ 1}\)): \(\displaystyle{ 1,o,o^2,...o^9}\) oraz 10 symetrii: \(\displaystyle{ s,so,so^2,...,so^9}\) - są to złożenia wielokrotności obrotu jednostkowego o kat \(\displaystyle{ \frac{\pi}{10}}\) oznaczonego symbolem \(\displaystyle{ o}\), z jedna z symetrii \(\displaystyle{ 10}\)-kata foremnego która oznaczamy symbolem \(\displaystyle{ s}\). Polowa tych symetrii nie ma żadnych stałych wierzchołków, są to symetrie względem symetralnych boków, druga polowa ma po \(\displaystyle{ 2}\) punkty stale będące naprzeciwległymi wierzchołkami lezącymi na osi symetrii.
Możemy teraz przystąpić do zliczania orbit: \(\displaystyle{ N}\).
Element neutralny \(\displaystyle{ 1}\) trzyma wszystkie kolorowania wiec \(\displaystyle{ S(1)=840}\). Jako ze jest tylko jeden wierzchołek koloru czerwonego, każda izometria nie ruszająca kolorowania musi mieć \(\displaystyle{ 1}\) wierzchołek stały. Takie izometrie to symetrie względem osi łączących naprzeciwlegle wierzchołki, których to symetrii jest \(\displaystyle{ 5}\), powiedzmy, ze są to \(\displaystyle{ \{s_1,s_2,s_3,s_3,s_5\}}\). 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 \(\displaystyle{ 3}\)) czyli takich kolorowań jest \(\displaystyle{ S(s_i)=8}\) dla \(\displaystyle{ i=1,2,3,4,5}\): 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.
\(\displaystyle{ N=\frac{S(e)+S(s_1)+...+S(s_5)}{|D_{10}|}=\frac{840+5\cdot 8}{20}=44}\).
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 \(\displaystyle{ 4}\), 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ę \(\displaystyle{ S_4}\) 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ć \(\displaystyle{ S_4\times C_2}\).
Wszystkich kolorowań spełniających warunki zadania jest tyle, ile kolorowań ścian spotykających się w jednym z wierzchołków, czyli \(\displaystyle{ 27}\).
Teraz zbieramy dane o kolorowaniach stałych dla poszczególnych izometrii. Przyda nam się w tym celu pogrupowanie elementów \(\displaystyle{ S_4}\) w klasy sprzężoności:
- identyczność (\(\displaystyle{ 1}\) sztuka) \(\displaystyle{ \rightarrow}\) \(\displaystyle{ 27}\) kolorowań stałych.
- obroty o \(\displaystyle{ \pm\pi/2}\) wokół osi łączących środki ścian (\(\displaystyle{ 6}\) sztuk) \(\displaystyle{ \rightarrow}\) po \(\displaystyle{ 9}\) kolorowań stałych, para naprzeciwległych ścian przechodzi w siebie, pozostałe muszą być jednobarwne.
- obroty o \(\displaystyle{ \pi}\) wokół osi łączących środki przeciwległych ścian (\(\displaystyle{ 3}\) sztuki) \(\displaystyle{ \rightarrow}\) po \(\displaystyle{ 27}\) kolorowania stałych, bo zachowują przeciwlegle ściany.
- obroty o \(\displaystyle{ \pi}\) wokół osi łączących środki przeciwległych krawędzi (\(\displaystyle{ 6}\) sztuk) \(\displaystyle{ \rightarrow}\) po \(\displaystyle{ 9}\) kolorowania stałych, bo zachowują parę naprzeciwległych ścian, zaś pozostałe muszą być jednobarwne.
- obroty wokół przekątnych sześcianu (o kat \(\displaystyle{ \frac{2\pi}{3}}\) patrząc wzdłuż osi) (\(\displaystyle{ 8}\) sztuk)\(\displaystyle{ \rightarrow}\) po \(\displaystyle{ 3}\) kolorowania stale, bo wszystkie ściany muszą być jednego koloru.