rekurencyjna postać..

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
kamzeso
Użytkownik
Użytkownik
Posty: 65
Rejestracja: 31 maja 2009, o 13:32
Płeć: Mężczyzna
Podziękował: 27 razy

rekurencyjna postać..

Post autor: kamzeso »

Niech \(\displaystyle{ c _{n}}\) dla \(\displaystyle{ n \ge 1}\) oznacza liczbę ciągów długości \(\displaystyle{ n}\) o elementach ze zbioru \(\displaystyle{ \{0,1,2,3 \}}\), które zawierają parzystą liczbę zer. Wyprowadź zależność rekurencyjną jaką spełniają liczby \(\displaystyle{ c _{n}}\).

proszę o pomoc..
Awatar użytkownika
Zordon
Użytkownik
Użytkownik
Posty: 4977
Rejestracja: 12 lut 2008, o 21:42
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 75 razy
Pomógł: 910 razy

rekurencyjna postać..

Post autor: Zordon »

zauważ, że \(\displaystyle{ c_n+d_n=4^n}\), gdzie \(\displaystyle{ d_n}\) to liczba ciągów o nieparzystej liczbie zer.
kamzeso
Użytkownik
Użytkownik
Posty: 65
Rejestracja: 31 maja 2009, o 13:32
Płeć: Mężczyzna
Podziękował: 27 razy

rekurencyjna postać..

Post autor: kamzeso »

Zordon pisze:zauważ, że \(\displaystyle{ c_n+d_n=4^n}\), gdzie \(\displaystyle{ d_n}\) to liczba ciągów o nieparzystej liczbie zer.
czyli ciągów z nieparzystą liczbą zer jest \(\displaystyle{ 4 ^{n} - c _{n}}\)
a ciągów z parzystą liczbą zer (chyba tutaj będą 2 przypadki):
1. gdy nie mamy zer, czyli jest ich 0
2. gdy mamy parzystą liczbę zer.
czyli ogólnie to będzie \(\displaystyle{ c _{n+1} = 2c _{n} + 4 ^{n} - c _{n} = c _{n} + 4 ^{n}}\)

czy w taki sposób się to wyznacza, czy jakoś inaczej??
Awatar użytkownika
Zordon
Użytkownik
Użytkownik
Posty: 4977
Rejestracja: 12 lut 2008, o 21:42
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 75 razy
Pomógł: 910 razy

rekurencyjna postać..

Post autor: Zordon »

Hmm, nie wiem po co tamte dwa przypadki...
Jak powstają ciągi długości n+1 o parzystej liczbie zer? Albo dołączamy do ciągu n elementowego o parzystej liczbie zer jedną z cyfr 1,2,3, albo do ciągu o nieparzystej liczbie zer dołączamy zero. Czyli:
\(\displaystyle{ c_{n+1}=3\cdot c_n+(4^n-c_n)=...}\)
ODPOWIEDZ