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..
rekurencyjna postać..
-
- Użytkownik
- Posty: 65
- Rejestracja: 31 maja 2009, o 13:32
- Płeć: Mężczyzna
- Podziękował: 27 razy
rekurencyjna postać..
czyli ciągów z nieparzystą liczbą zer jest \(\displaystyle{ 4 ^{n} - c _{n}}\)Zordon pisze:zauważ, że \(\displaystyle{ c_n+d_n=4^n}\), gdzie \(\displaystyle{ d_n}\) to liczba ciągów o nieparzystej liczbie zer.
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??
- Zordon
- 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ć..
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)=...}\)
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)=...}\)