Niech \(\displaystyle{ a_n}\) oznacza ilość ciągów (wariacji z powtórzeniami) liter \(\displaystyle{ A,B,C,D}\) długości \(\displaystyle{ n}\), w których nie występują 2 litery A obok siebie.Znajdź rekurencję oraz warunki początkowe dla \(\displaystyle{ a_n}\).
Próbowałam to rozpisać i dla:
\(\displaystyle{ n=1}\) jest ich \(\displaystyle{ 4}\)
\(\displaystyle{ n=2}\) jest \(\displaystyle{ 15}\)
\(\displaystyle{ n=3}\) jest \(\displaystyle{ 33}\) ... jednak nie potrafię złożyć tego w jakikolwiek wzór W jaki sposób zrobić to zadanie?
Ilość ciągów
-
Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Re: Ilość ciągów
Niech \(\displaystyle{ x_n}\) oznacza liczbę (nie ilość) ciągów długości \(\displaystyle{ n}\) spełniających warunki zadania i kończących się literą A, zaś \(\displaystyle{ y_n}\) oznacza liczbę ciągów długości \(\displaystyle{ n}\) spełniających warunki zadania i niekończących się literą A.
Oczywiście mamy \(\displaystyle{ a_n=x_n+y_n}\), a ponadto
\(\displaystyle{ a_{n+1}=3x_n+4y_n \ (*)}\) (do ciągu niekończącego się literą A dopisujemy na cztery sposoby ostatnią literę i dalej mamy ciąg spełniający warunki zadania, bądź do ciągu kończącego się literą A dopisujemy na trzy sposoby ostatnią literę) oraz
\(\displaystyle{ x_{n+1}=3y_n}\) (do ciągu długości \(\displaystyle{ n}\) spełniającego warunki zadania i niekończącego się literą A dopisujemy literę A na końcu, uzyskując ciąg długości \(\displaystyle{ n+1}\) spełniający warunki zadania i kończący się literą A), czyli podstawiając do \(\displaystyle{ (*)}\) z dwóch pozostałych równości mamy
\(\displaystyle{ x_{n+1}+y_{n+1}=3x_n+4y_n\\3y_n+y_{n+1}=9y_{n-1}+4y_n\\y_{n+1}=y_n+9y_{n-1}}\)
Ponadto nietrudno przekonać się, że \(\displaystyle{ y_1=3, \ y_2=12}\) (jeśli chodzi o \(\displaystyle{ y_2}\), na trzy sposoby wybieramy drugą literę ze zbioru \(\displaystyle{ \left\{B,C, D \right\}}\), a na pierwszym miejscu może być dowolna z czterech).
Równanie rekurencyjne
\(\displaystyle{ y_{n+1}=y_n+9y_{n-1}, \ y_1=3, \ y_2=12}\)
to coś, z czym powinnaś sobie poradzić, np. za pomocą równania charakterystycznego lub funkcji tworzących.
A jak już masz wzór jawny na \(\displaystyle{ y_n}\), to \(\displaystyle{ a_n=x_n+y_n=3y_{n-1}+y_n}\) dla \(\displaystyle{ n\ge 2}\).
Pewnie nie jest to najprostszy sposób, ale zawsze jakiś…
Oczywiście mamy \(\displaystyle{ a_n=x_n+y_n}\), a ponadto
\(\displaystyle{ a_{n+1}=3x_n+4y_n \ (*)}\) (do ciągu niekończącego się literą A dopisujemy na cztery sposoby ostatnią literę i dalej mamy ciąg spełniający warunki zadania, bądź do ciągu kończącego się literą A dopisujemy na trzy sposoby ostatnią literę) oraz
\(\displaystyle{ x_{n+1}=3y_n}\) (do ciągu długości \(\displaystyle{ n}\) spełniającego warunki zadania i niekończącego się literą A dopisujemy literę A na końcu, uzyskując ciąg długości \(\displaystyle{ n+1}\) spełniający warunki zadania i kończący się literą A), czyli podstawiając do \(\displaystyle{ (*)}\) z dwóch pozostałych równości mamy
\(\displaystyle{ x_{n+1}+y_{n+1}=3x_n+4y_n\\3y_n+y_{n+1}=9y_{n-1}+4y_n\\y_{n+1}=y_n+9y_{n-1}}\)
Ponadto nietrudno przekonać się, że \(\displaystyle{ y_1=3, \ y_2=12}\) (jeśli chodzi o \(\displaystyle{ y_2}\), na trzy sposoby wybieramy drugą literę ze zbioru \(\displaystyle{ \left\{B,C, D \right\}}\), a na pierwszym miejscu może być dowolna z czterech).
Równanie rekurencyjne
\(\displaystyle{ y_{n+1}=y_n+9y_{n-1}, \ y_1=3, \ y_2=12}\)
to coś, z czym powinnaś sobie poradzić, np. za pomocą równania charakterystycznego lub funkcji tworzących.
A jak już masz wzór jawny na \(\displaystyle{ y_n}\), to \(\displaystyle{ a_n=x_n+y_n=3y_{n-1}+y_n}\) dla \(\displaystyle{ n\ge 2}\).
Pewnie nie jest to najprostszy sposób, ale zawsze jakiś…