Sześciokąt foremny uzupełniamy o jego środek \(\displaystyle{ O}\) oraz \(\displaystyle{ 6}\) promieni, łączących punkt \(\displaystyle{ O}\) z wierzchołkami sześciokąta. Ile jest w otrzymanym grafie tras zamkniętych(krawędzie mogą się powtarzać) długości \(\displaystyle{ n}\) prowadzących z \(\displaystyle{ O}\) do \(\displaystyle{ O}\)? Należy ułożyć odpowiednie równanie rekurencyjne i rozwiązać je.
Proszę o sprawdzenie poniższego rozwiązania:
Niech \(\displaystyle{ S_n}\) oznacza liczbę tras zamkniętych z \(\displaystyle{ O}\) do \(\displaystyle{ O}\) długości \(\displaystyle{ n}\). Sprawdzam po kolei wartość \(\displaystyle{ S_n}\) dla kilku początkowych wartości \(\displaystyle{ n}\).
\(\displaystyle{ S_0=1}\)
\(\displaystyle{ S_1=0}\)
\(\displaystyle{ S_2=6}\) bo mamy sześć tras dwukrokowych(tyle co promieni, po pierwszym kroku jesteśmy w którym z wierzchołków i w drugim kroku musimy wrócić do środka).
\(\displaystyle{ S_3=6 \cdot 2=12}\) bo w pierwszym kroku mamy \(\displaystyle{ 6}\) możliwości i po tym kroku znajdujemy się w którymś z wierzchołków sześciokąta i następny krok możemy wykonać w prawo lub w lewo na \(\displaystyle{ 2}\) możliwości, a w następnym kroku już nie mamy wyboru-musimy wrócić do środka, zatem jest \(\displaystyle{ 6 \cdot 2}\) możliwości.
\(\displaystyle{ S_4=6 \cdot s_2+6 \cdot 2 \cdot 2=60}\) bo pierwszy krok możemy znowu wykonać na sześć możliwości po którym jesteśmy w którymś z wierzchołków i teraz jeśli w drugim kroku wracamy do środka to powracamy do \(\displaystyle{ S_2}\) możliwości czyli będzie już \(\displaystyle{ 6 \cdot S_2}\), a jeśli w drugim kroku idziemy w prawo bądź lewo to mamy dwie możliwości po czym znowu znajdujemy się w którymś z wierzchołków i teraz nie możemy iść do środka, musimy iść znowu w prawo bądź lewo czyli dwie możliwości. Czyli \(\displaystyle{ S_4=6 \cdot s_2+6 \cdot 2 \cdot 2=60}\).
\(\displaystyle{ S_5=6 \cdot S_3+6 \cdot 2 \cdot S_3+6 \cdot 2 \cdot 2 \cdot S_2+6 \cdot 2 \cdot 2 \cdot 2 \cdot 2=192}\) bo znowu w pierwszym kroku mamy \(\displaystyle{ 6}\) możliwości i jeśli w drugim wracamy do środka to dostajemy \(\displaystyle{ S_3}\), a jeśli w drugim kroku idziemy w prawo bądź lewo czyli dwie możliwości i potem wracamy do środka to dostajemy \(\displaystyle{ S_2}\), a jeśli w trzecim kroku znowu idziemy w prawo bądź lewo to znów dwie możliwości i w czwartym kroku już nie mamy wyboru.
\(\displaystyle{ S_6=6 \cdot S_4+6 \cdot 2 \cdot S_3+6 \cdot 2 \cdot 2 \cdot S_2+6 \cdot 2 \cdot 2 \cdot 2 \cdot 2 \cdot =744}\) bo znowu w pierwszym \(\displaystyle{ 6}\) możliwości i jeśli w drugim w wracamy to dostajemy \(\displaystyle{ S_4}\), a jeśli w drugim w prawo bądź lewo (2 możliwości) to jeśli w trzecim wracamy to \(\displaystyle{ S_3}\), a jeśli w trzecim w prawo bądź lewo (2 możliwości) i w czwartym wracamy to \(\displaystyle{ S_2}\) i jeśli w czwartym w lewo bądź prawo (2 możliwości) to w piątym musimy już w lewo bądź prawo (2 możliwości) i w szóstym wracamy. Widać zatem, że \(\displaystyle{ S_n=6S_{n-2}+6 \cdot 2 \cdot S_{n-3}+6 \cdot 2 \cdot 2 \cdot S_{n-4}+...+6 \cdot 2^{n-2}}\), ale biorąc pod uwagę, że \(\displaystyle{ S_1=0, S_0=1}\) możemy napisać, że \(\displaystyle{ S_n=6S_{n-2}+2 \cdot 6S_{n-3}+2 \cdot 2 \cdot 6S_{n-4}+...+2^{n-3} \cdot 6S_1+2^{n-2} \cdot 6S_0}\). Widzimy zatem, że ciąg będzie zdefiniowany rekurencyjnie przez \(\displaystyle{ S_n=6S_{n-2}+2 \cdot S_{n-1}}\). Czyli przewidujemy \(\displaystyle{ S_n=q^n}\) i wstawiamy do równania otrzymując: \(\displaystyle{ q^n-2q^{n-1}-6q^{n-2}=0}\) czyli \(\displaystyle{ q^2-2q-6=0}\). Rozwiązaniami są \(\displaystyle{ q_1=-1- \sqrt{7}}\) i \(\displaystyle{ q_2=-1+ \sqrt{7}}\). Rozwiązanie \(\displaystyle{ S_n}\) przewidujemy w postaci \(\displaystyle{ S_n=cq_1^n+dq_2^n}\). Podstawiając warunki początkowe otrzymujemy, że \(\displaystyle{ S_n= \frac{7- \sqrt{7} }{14}\left( -1- \sqrt{7} \right)^n+ \frac{7+ \sqrt{7} }{14}\left( -1+ \sqrt{7} \right)^n}\).
Czy tak jest dobrze?