Lemat Burnside'a ( ile pokolorowań kwadratu )

[szymonidlo]

Witam,

Mam problem przy zadaniu o treści:
Na ile istotnie różnych kolorów można pokolorować kwadrat 3x3 (czyli złożony z 9 mniejszych kwadratów) za pomocą 3 kolorów, jeżeli dwa pokolorowania uznajemy za równoważne, gdy jedno z nich można otrzymać z drugiego przez a) obrót, b) obrót lub symetrię.

Moje rozwiązanie wygląda następująco:

Względem obrotu o kąt:

\(\displaystyle{ Fix}\) \(\displaystyle{ O_{0^{o}} =}\) \(\displaystyle{ Fix}\) \(\displaystyle{ O_{360^{o}} = 3^{9}}\)

\(\displaystyle{ \left[\begin{array}{ccc}A&B&C\\D&E&F\\G&H&I\end{array}\right]}\)

\(\displaystyle{ Fix}\) \(\displaystyle{ O_{90^{o}} = 3^{3}}\)

\(\displaystyle{ \left[\begin{array}{ccc}C&B&C\\B&A&B\\C&B&C\end{array}\right]}\)

\(\displaystyle{ Fix}\) \(\displaystyle{ O_{180^{o}} = 3^{5}}\)

\(\displaystyle{ \left[\begin{array}{ccc}B&D&A\\E&C&E\\A&D&B\end{array}\right]}\)

\(\displaystyle{ Fix}\) \(\displaystyle{ O_{270^{o}} = 3^{3}}\)

\(\displaystyle{ \left[\begin{array}{ccc}C&B&C\\B&A&B\\C&B&C\end{array}\right]}\)

I względem symetrii:

\(\displaystyle{ Fix}\) \(\displaystyle{ S_{|} = 3^{6}}\) (Pionowa)

\(\displaystyle{ \left[\begin{array}{ccc}A&C&A\\B&E&B\\D&F&D\end{array}\right]}\)

\(\displaystyle{ Fix}\) \(\displaystyle{ S_{-} = 3^{6}}\) (Pozioma)

\(\displaystyle{ \left[\begin{array}{ccc}A&B&D\\C&E&F\\A&B&D\end{array}\right]}\)

\(\displaystyle{ Fix}\) \(\displaystyle{ S_{/} = 3^{6}}\) (Ukośna 1)

\(\displaystyle{ \left[\begin{array}{ccc}A&B&D\\C&E&B\\F&C&A\end{array}\right]}\)

\(\displaystyle{ Fix}\) \(\displaystyle{ S_{\setminus } = 3^{6}}\) (Ukośna 2)

\(\displaystyle{ \left[\begin{array}{ccc}D&B&A\\B&E&C\\A&C&F\end{array}\right]}\)

Ostateczne wyniki to:

a) \(\displaystyle{ \frac{2* 3^{9} + 2 * 3^{3} + 3^{5} }{5}}\)
b) \(\displaystyle{ \frac{2* 3^{9} + 2 * 3^{3} + 3^{5} + 4 * 3^{6}}{9}}\)

Pytanie brzmi:

Czy dobrze, że uwzględniam Fix dla obrotu 0 i 360 stopni (pogrubione w wyniku) jako osobne przypadki i mianowniki wynoszą kolejno 5 i 9?

Czy wynik powinien wyglądać tak?
Drugi wynik:
a) \(\displaystyle{ \frac{3^{9} + 2 * 3^{3} + 3^{5} }{4}}\)
b) \(\displaystyle{ \frac{3^{9} + 2 * 3^{3} + 3^{5} + 4 * 3^{6}}{8}}\)

A może jeszcze inaczej? Proszę o pomoc w rozwiązaniu problemu, bo nie do końca to rozumiem.

[placky]

Drugi jest poprawny. W grupie obrotów kwadratu nie ma obrotu o \(\displaystyle{ 360 ^{o}}\).

[szymonidlo]

Dzięki za odpowiedź!

Jeszcze jedno pytanie, kiedy mamy do czynienia z obrotem o \(\displaystyle{ 360^{o}}\) i czy kiedykolwiek się to uwzględnia ?

[placky]

Obrót \(\displaystyle{ 0 ^{o}}\) i \(\displaystyle{ 360 ^{o}}\) to dokładnie to samo.

Zauważ, że grupy obrotów i symetrii to w zasadzie permutacje wierzchołków. W naszym przypadku mamy do czynienia z tzw. permutacją identycznościową (każdemu wierzchołkowi przyporządkowywany jest dokładnie ten sam wierzchołek). Nic się nie zmienia. Z tego też powodu często nie mówi się o "obrocie o \(\displaystyle{ 0 ^{o}}\)", a o przekształceniu identycznościowym, elemencie neutralnym. Jak łatwo zauważyć obroty \(\displaystyle{ 0 ^{o}}\) i \(\displaystyle{ 360 ^{o}}\) dają dokładnie tę samą permutację, podobnie jak obrót \(\displaystyle{ 90 ^{o}}\) i \(\displaystyle{ 450 ^{o}}\) etc. Nie ma więc potrzeby liczenia dwa razy tego samego.

[szymonidlo]

dzięki wielkie, potrzebowałem usystematyzować to, bo nie miałem pewności