Kolorowanie wierzchołków trójkąta lemat burnside'a

[yanan]

Witam

Mam problem z takim zadaniem

Dany jest trójkąt równoboczny, którego wszystkie trzy wierzchołki należy pokolorować. Dwa kolorowania uważamy za jednakowe, jeśli możemy jedno z nich otrzymać z drugiego za pomocą
odpowiedniego obrotu trójkąta.
Ile jest różnych sposobów pokolorowania wierzchołków naszego trójkąta
przy użyciu niektórych bądź wszystkich spośród danych k kolorów?

Wskazówką jest tutaj wykorzystanie lematu burnside'a

\(\displaystyle{ N= \frac{1}{|G|} \sum_{}^{} |fix(g)|}\)

G - grupa izometrii trójkąta

Zatem |G| = 6, bo mamy obroty o 0=360,60,120,240 st. + symetrie (3)

fix(g) - zbiór punktów stałych przekształcenia g, czyli w tym przypadku zbioru kolorowań, których przekształcenie g nie zmieni.

Problem polega na tym że nie mam takiej wyobraźni żeby omówić każdy z sytuacji dla konkretnego kąta i nie wiem jaki będzie końcowy wzór.

gdzieś wyczytałem takie coś, ale nie wiem czy to jest prawda i nie wiem skąd taki wzór
- Obrót o 0st.
Taki obrót zostawia trójkąt w spokoju. Wszystkich możliwości pokolorowania kwadratu k kolorami jest k^3, a gdy pokolorujemy, to obrót nic nie zmieni. Dlatego wszystkie możliwe kolorowania są punktami stałymi.

[porfirion]

Zsumujmy trzy rozłączne przypadki:
1) kolorujemy dokładnie jednym kolorem; jest tego \(\displaystyle{ k}\) różnych kolorowań
2) kolorujemy dokładnie dwoma kolorami; jest tego \(\displaystyle{ k(k-1)}\) kolorowań
3) kolorujemy dokładnie trzema kolorami; wyborów trzech kolorów jest \(\displaystyle{ {k\choose 3}}\) ale każde trzy kolory posłużą na dwa różne kolorowania.
Wychodzi \(\displaystyle{ k^{2}+2{k\choose 3}}\).

[Qń]

Ten sam wynik można uzyskać używając lematu Burnside'a.

Obroty trójkąta są tylko trzy: o \(\displaystyle{ 0^o, 120^o,240^o}\). W przypadku obrotu o zero stopni punktami stałymi są wszystkie \(\displaystyle{ k^3}\) pokolorowania. W pozostałych dwóch obrotach punktami stałymi są wyłącznie pokolorowania jednokolorowe, czyli jest ich po \(\displaystyle{ k}\). Odpowiedź to zatem:
\(\displaystyle{ \frac 13 (k^3+2k)}\)
i łatwo sprawdzić, że zgadza się ona z ręcznym rachunkiem porfiriona.

Q.

[yanan]

Ale to \(\displaystyle{ k^{3}}\) i \(\displaystyle{ k}\) we wzorze się jakoś wyprowadza czy to jest jakiś pewniak, że tak jest?

[Qń]

No jeśli każdy z trzech wierzchołków mamy pomalować na któryś z \(\displaystyle{ k}\) kolorów, to możliwości jest \(\displaystyle{ k\cdot k \cdot k=k^3}\) - formalnie wynika z to z . Natomiast jeśli wszystkie trzy wierzchołki mamy pomalować na ten sam kolor, to wystarczy na \(\displaystyle{ k}\) sposobów wybrać który to będzie kolor.

Jeśli chcesz zajmować się tematami na poziomie lematu Burnside'a, to taką elementarną szkolną kombinatorykę powinieneś umieć biegle.

Q.