Kolorowanie tortu

[squared]

Mam takie zadanie:
Koło dzielimy na \(\displaystyle{ n}\) wycinków (jak tort). Każdy wycinek malujemy jednym z czterech kolorów: żółty, zielony, czerwony i niebieski, w taki sposób, żeby żadne dwie sąsiednie części nie były tego samego koloru. Niech \(\displaystyle{ S_{n}}\) oznacza liczbę taki różnych możliwych kolorowań.
a) Określić \(\displaystyle{ S_{n}}\) rekurencyjnie (zależność II rzędu dla \(\displaystyle{ n \ge 2}\)
b) Podać jawny wzór na \(\displaystyle{ S_{n}}\) dla n \(\displaystyle{ \ge 2}\)

Zacząłem po kolei rozważać:

dla \(\displaystyle{ n=1 \Rightarrow S_{1} = {4 \choose 4} = 1}\)
Cały tort pokolorowany na jeden kolor - więc 4 możliwości.

dla \(\displaystyle{ n=2 \Rightarrow S_{2} = {4 \choose 2} = 6}\)
Mamy dwie części, jedną koloruję na jeden kolor, drugą na inny kolor, więc wybieram 2 kolor z 4.


dla \(\displaystyle{ n=3 \Rightarrow S_{3} = {4 \choose 3} = 4}\)
Jest jedna możliwość - każda część na inny kolor pokolorowana - zatem wybór 3 kolorów z 4.

dla \(\displaystyle{ n=4}\)
1. Każdą część koloruję innym kolorem - mnożę przez dwa, ponieważ mogę zmienić kolejność sąsiadujących kolorów (na rysunku ładnie to wychodzi): \(\displaystyle{ {4 \choose 4} \cdot 2= 2}\)
2. Dwie części koloruję na ten sam kolor, dwie pozostałe na dwa inne. (Jeden kolor się jest naprzeciwko siebie) \(\displaystyle{ {4 \choose 3} \cdot {4\choose 1}}\)
3. Koloruję dwoma kolorami. Dwie ćwiartki naprzeciw siebie są tego samego koloru: \(\displaystyle{ {4 \choose 2} = 6}\)
Zatem \(\displaystyle{ S_{4}=24}\)

Czy to jest dobrze zrobione? I wtedy liczę \(\displaystyle{ S_{4} = S_{3} a + b S_{2} \Leftrightarrow 24= 4a + 6b \Leftrightarrow a = -12 \wedge b=12 \Rightarrow S_{n} = -12S_{n-1} + 12 S_{n-2}}\).

Po pierwsze nie wiem, czy dobrze rozważyłem wszystkie przypadki. Dwa, już wniosek końcowy o zależności rekurencyjnej dla mnie jest absurdalny, chociaż cuda się zdażają, więc może dobrze? Ktoś sprawdzi/doradzi/pomoże?

[norwimaj]

Niech \(\displaystyle{ S_{n}}\) oznacza liczbę taki różnych możliwych kolorowań.

Jakie kolorowania uznajemy za różne?

dla \(\displaystyle{ n=1 \Rightarrow S_{1} = {4 \choose 4} = 1}\)
Cały tort pokolorowany na jeden kolor - więc 4 możliwości.

To w końcu \(\displaystyle{ 1}\) czy \(\displaystyle{ 4}\)?

I wtedy liczę \(\displaystyle{ S_{4} = S_{3} a + b S_{2} \Leftrightarrow 24= 4a + 6b \Leftrightarrow a = -12 \wedge b=12 \Rightarrow S_{n} = -12S_{n-1} + 12 S_{n-2}}\).

Na jakiej podstawie wnioskujesz, że istnieje taka zależność rekurencyjna?

[squared]

Jakie kolorowania uznajemy za różne?

Hmmm nie wiem co masz na myśli. No wyobraź sobie tort jak jets podzielony i kolorujemy każdą część na dowolny kolor, tak by sąsiednie części miały inny kolor. Jeśli masz na myśli kolejność to jeśli np. mamy dwie części tylko i np. na niebiesko jedną kolorujemy, drugą na czerwono to jeden sposób. Pokolorowanie na odwrót - najpierw na czerwono, potem na niebiesko, daje ten sam sposób kolorowania tortu. Nie wiem, czy o to pytałeś, nie potrafię nic dodać na ten temat.
Jakie kolorowania uznajemy za różne?

To w końcu \(\displaystyle{ 1}\) czy \(\displaystyle{ 4}\)?

Oczywiście, że 4. To po prostu źle mi się napisało.

Na jakiej podstawie wnioskujesz, że istnieje taka zależność rekurencyjna?

W sumie to nie wiem, o to w sumie pytam

[norwimaj]

Pokolorowanie na odwrót - najpierw na czerwono, potem na niebiesko, daje ten sam sposób kolorowania tortu. Nie wiem, czy o to pytałeś, nie potrafię nic dodać na ten temat.

Właśnie o to. Wygląda na to, że utożsamiasz dwa kolorowania, jeśli jedno powstało z drugiego przez izometrię. Przy tej interpretacji chyba będzie ciężko o jakąś zależność rekurencyjną. Moim zdaniem autorowi zadania chodziło o interpretację bez żadnego utożsamiania kolorowań.

dla \(\displaystyle{ n=4}\)
1. Każdą część koloruję innym kolorem - mnożę przez dwa, ponieważ mogę zmienić kolejność sąsiadujących kolorów (na rysunku ładnie to wychodzi): \(\displaystyle{ {4 \choose 4} \cdot 2= 2}\)

No nie, na taki wynik się nie zgodzę przy żadnej interpretacji. Naprzeciw koloru żółtego może być jeden z trzech kolorów.

2. Dwie części koloruję na ten sam kolor, dwie pozostałe na dwa inne. (Jeden kolor się jest naprzeciwko siebie) \(\displaystyle{ {4 \choose 3} \cdot {4\choose 1}}\)

Również się nie zgadzam.

[squared]

2. Dwie części koloruję na ten sam kolor, dwie pozostałe na dwa inne. (Jeden kolor się jest naprzeciwko siebie) \(\displaystyle{ {4 \choose 3} \cdot {4\choose 1}}\)

Również się nie zgadzam.

Oczywiście miało być\(\displaystyle{ {4 \choose 2} \cdot {4\choose 1}}\)

dla \(\displaystyle{ n=4}\)
1. Każdą część koloruję innym kolorem - mnożę przez dwa, ponieważ mogę zmienić kolejność sąsiadujących kolorów (na rysunku ładnie to wychodzi): \(\displaystyle{ {4 \choose 4} \cdot 2= 2}\)

No nie, na taki wynik się nie zgodzę przy żadnej interpretacji. Naprzeciw koloru żółtego może być jeden z trzech kolorów.

Jak teraz rozrysowałem sobie na kartce, czy mają być 3 takie sposoby?

[norwimaj]

Oczywiście miało być\(\displaystyle{ {4 \choose 2} \cdot {4\choose 1}}\)

Na pewno?

Jak teraz rozrysowałem sobie na kartce, czy mają być 3 takie sposoby?

Ok.

A ustosunkujesz się jakoś do tego?

Przy tej interpretacji chyba będzie ciężko o jakąś zależność rekurencyjną. Moim zdaniem autorowi zadania chodziło o interpretację bez żadnego utożsamiania kolorowań.

[squared]

No ja to tak zinterpretowałem: wybieram trzy kolory, bo tylu użyję do pokolorowania, potem wybieram ten co się powtórzy.

No do tego co napisałeś, to co mam powiedzieć. Skoro tak uważasz, to pewnie tak jest, ale wtedy wszystkie moje rozważania są błędne i trzeba wliczyć te powtórzenia...

[norwimaj]

No ja to tak zinterpretowałem: wybieram trzy kolory, bo tylu użyję do pokolorowania, potem wybieram ten co się powtórzy.

Czyli dosłownie \(\displaystyle{ \binom43\cdot\binom31}\).

[squared]

No to miałem na myśli, ale jakoś nie wiem czemu tak dziwnie to zapisałem, wracając jednak do tematu przewodniego. To w takim razie trzeba wszystkie rozważania cofnąć, bo nie wyjdzie rekurencja?