Ile jest różnych ciągów ternarnych (tj.składających się z 0,1,2) o długości n, takich że po
cyfrach 0 lub 1 zawsze stoi 2? Uloz odpowiednie rownanie rekurencyjne i rozwiaz je.
Nie mam pojęcia jak się za to wziąć:/
Rekurencja ciągu ternarnego
-
- Użytkownik
- Posty: 11
- Rejestracja: 20 sty 2015, o 00:41
- Płeć: Kobieta
- Lokalizacja: Kraków
- Podziękował: 5 razy
- vpprof
- Użytkownik
- Posty: 492
- Rejestracja: 11 paź 2012, o 11:20
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 26 razy
- Pomógł: 64 razy
Rekurencja ciągu ternarnego
No jeśli rekurencja, to musisz się zastanowić, jakimi sposobami z ciągu \(\displaystyle{ n}\)-wyrazowego można utworzyć ciąg \(\displaystyle{ n+1}\)-wyrazowy — czyli co można dopisać na końcu i ile \(\displaystyle{ n+1}\)-wyrazowych ciągów można utworzyć z każdego \(\displaystyle{ n}\)-wyrazowego. To będzie twoje równanie rekurencyjne.
Potem wstawiasz warunek brzegowy, czyli pokazujesz, że dla \(\displaystyle{ n=1}\) są \(\displaystyle{ 3}\) możliwe ciągi: \(\displaystyle{ 0,\ 1,\ 2}\) i gotowe.
Oznacz sobie jakoś liczbę ciągów \(\displaystyle{ n}\)-wyrazowych, np. \(\displaystyle{ f(n)}\).
EDIT: Acha, masz jeszcze rozwiązać rekurencję. Najłatwiej funkcjami tworzącymi. Ale najpierw w ogóle dojdź do tej rekurencji
Potem wstawiasz warunek brzegowy, czyli pokazujesz, że dla \(\displaystyle{ n=1}\) są \(\displaystyle{ 3}\) możliwe ciągi: \(\displaystyle{ 0,\ 1,\ 2}\) i gotowe.
Oznacz sobie jakoś liczbę ciągów \(\displaystyle{ n}\)-wyrazowych, np. \(\displaystyle{ f(n)}\).
EDIT: Acha, masz jeszcze rozwiązać rekurencję. Najłatwiej funkcjami tworzącymi. Ale najpierw w ogóle dojdź do tej rekurencji
- arek1357
- Użytkownik
- Posty: 5740
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 130 razy
- Pomógł: 525 razy
Rekurencja ciągu ternarnego
\(\displaystyle{ \sum_{i=1}^{ \infty }a_{n+1}x^n=2\sum_{i=1}^{ \infty }a_{n}x^n+ \sum_{i=1}^{ \infty }(-1)^nx^n}\)
\(\displaystyle{ \frac{1}{x} \sum_{i=1}^{ \infty }a_{n+1}x^{n+1}=2\sum_{i=1}^{ \infty }a_{n}x^n+ \sum_{i=1}^{ \infty }(-1)^nx^n}\)
\(\displaystyle{ \frac{1}{x}( \sum_{i=1}^{ \infty }a_{n}x^{n}-a_{1}x)=2\sum_{i=1}^{ \infty }a_{n}x^n+ \sum_{i=1}^{ \infty }(-1)^nx^n}\)
niech:
\(\displaystyle{ S= \sum_{i=1}^{ \infty }a_{n}x^{n}}\)
mamy:
\(\displaystyle{ \frac{1}{x}S-3=2S+\sum_{i=1}^{ \infty }(-1)^nx^n}\)
\(\displaystyle{ S( \frac{1}{x}-2 )=3- \frac{x}{1+x}}\)
Po przekształceniach:
\(\displaystyle{ S=-x \frac{2x+3}{2(x+1)(x- \frac{1}{2} )}}\)
\(\displaystyle{ \frac{1}{x} \sum_{i=1}^{ \infty }a_{n+1}x^{n+1}=2\sum_{i=1}^{ \infty }a_{n}x^n+ \sum_{i=1}^{ \infty }(-1)^nx^n}\)
\(\displaystyle{ \frac{1}{x}( \sum_{i=1}^{ \infty }a_{n}x^{n}-a_{1}x)=2\sum_{i=1}^{ \infty }a_{n}x^n+ \sum_{i=1}^{ \infty }(-1)^nx^n}\)
niech:
\(\displaystyle{ S= \sum_{i=1}^{ \infty }a_{n}x^{n}}\)
mamy:
\(\displaystyle{ \frac{1}{x}S-3=2S+\sum_{i=1}^{ \infty }(-1)^nx^n}\)
\(\displaystyle{ S( \frac{1}{x}-2 )=3- \frac{x}{1+x}}\)
Po przekształceniach:
\(\displaystyle{ S=-x \frac{2x+3}{2(x+1)(x- \frac{1}{2} )}}\)