Cześć,
Mam zadanie: Ile jest \(\displaystyle{ n}\)-elementowych ciągów, których wyrazy należą do zbioru \(\displaystyle{ \left\{ 1,2,3,4,5\right\}}\) takich, że po każdej z cyfr \(\displaystyle{ 3,4,5}\) zawsze następuje cyfra \(\displaystyle{ 1}\)?
Wydaje mi się, że trzeba to zrobić rekurencyjnie, ale nie mogę jej ułożyć. Proszę o pomoc
Rekurencja- ciągi liczb
-
malinka1020
- Użytkownik
- Posty: 3
- Rejestracja: 24 kwie 2019, o 20:43
- Płeć: Kobieta
- Lokalizacja: Warszawa
- Podziękował: 1 raz
-
kerajs
- Użytkownik
- Posty: 8585
- Rejestracja: 17 maja 2013, o 10:23
- Płeć: Mężczyzna
- Podziękował: 307 razy
- Pomógł: 3351 razy
Re: Rekurencja- ciągi liczb
Tworzę pary \(\displaystyle{ 31 \ , \ 41 \ , \ 51}\)
Par wśród n liczb może być od \(\displaystyle{ 0}\) do \(\displaystyle{ \lfloor \frac n2 \rfloor}\)
Zakładam że jest \(\displaystyle{ k}\) par (gdzie \(\displaystyle{ k \le \lfloor \frac n2 \rfloor}\)). Ilość różnych ciągów złożonych z \(\displaystyle{ k}\) par to \(\displaystyle{ 3^k}\). Na końce tego ciągu i między jego wyrazy można wstawić dodatkowe jedynki i dwójki które mogę ustawić w ciąg na \(\displaystyle{ 2^{n-2k}}\) sposobów. Tych miejsc jest \(\displaystyle{ k+1}\), a ilość przydziałów jest równoważna ilości naturalnych (dla mnie zero jest naturalne) rozwiązań równania \(\displaystyle{ x_1+x_2+...+x_{k+1}=n-2k}\), czyli \(\displaystyle{ {(n-2k)+(k+1)-1 \choose (k+1)-1}}\)
Ostatecznie ilość szukanych ciągów to:
\(\displaystyle{ il= \sum_{k=0}^{\lfloor \frac n2 \rfloor} {n-k \choose k} 3^k2^{n-2k}}\)
Par wśród n liczb może być od \(\displaystyle{ 0}\) do \(\displaystyle{ \lfloor \frac n2 \rfloor}\)
Zakładam że jest \(\displaystyle{ k}\) par (gdzie \(\displaystyle{ k \le \lfloor \frac n2 \rfloor}\)). Ilość różnych ciągów złożonych z \(\displaystyle{ k}\) par to \(\displaystyle{ 3^k}\). Na końce tego ciągu i między jego wyrazy można wstawić dodatkowe jedynki i dwójki które mogę ustawić w ciąg na \(\displaystyle{ 2^{n-2k}}\) sposobów. Tych miejsc jest \(\displaystyle{ k+1}\), a ilość przydziałów jest równoważna ilości naturalnych (dla mnie zero jest naturalne) rozwiązań równania \(\displaystyle{ x_1+x_2+...+x_{k+1}=n-2k}\), czyli \(\displaystyle{ {(n-2k)+(k+1)-1 \choose (k+1)-1}}\)
Ostatecznie ilość szukanych ciągów to:
\(\displaystyle{ il= \sum_{k=0}^{\lfloor \frac n2 \rfloor} {n-k \choose k} 3^k2^{n-2k}}\)
-
arek1357
- Użytkownik
- Posty: 5749
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Re: Rekurencja- ciągi liczb
Coś mi tu nie pasi u Ciebie dla\(\displaystyle{ n=2}\) (ciągi dwucyfrowe) wychodzi siedem...
\(\displaystyle{ \sum_{k=0}^{1} {2-k \choose k}3^k2^{2-2k}=7}\)
ciągów dwucyfrowych może jednak być:
\(\displaystyle{ 11,12,13,14,15,21,22,23,24,25,31,41,51}\)
Czyli trzynaście...
Nie jest nigdzie w końcu powiedziane, że po jedynce i dwójce jedynka nie może zaistnieć
\(\displaystyle{ \sum_{k=0}^{1} {2-k \choose k}3^k2^{2-2k}=7}\)
ciągów dwucyfrowych może jednak być:
\(\displaystyle{ 11,12,13,14,15,21,22,23,24,25,31,41,51}\)
Czyli trzynaście...
Nie jest nigdzie w końcu powiedziane, że po jedynce i dwójce jedynka nie może zaistnieć
-
kerajs
- Użytkownik
- Posty: 8585
- Rejestracja: 17 maja 2013, o 10:23
- Płeć: Mężczyzna
- Podziękował: 307 razy
- Pomógł: 3351 razy
Rekurencja- ciągi liczb
I nie tylko te.
Najwyraźniej odmiennie interpretujemy fragment:
Dlatego nie zliczam czerwonych ciągów:
Najwyraźniej odmiennie interpretujemy fragment:
Dla mnie oznacza to, że ciąg nie może kończyć się jedną z cyfr \(\displaystyle{ 3,4,5}\) gdyż musi po niej nastąpić cyfra \(\displaystyle{ 1}\).malinka1020 pisze: takich, że po każdej z cyfr \(\displaystyle{ 3,4,5}\) zawsze następuje cyfra \(\displaystyle{ 1}\)?
Dlatego nie zliczam czerwonych ciągów:
, zaś czarnych (które zliczam) jest 7 (czyli tyle samo, ile generuje wzorek z sumą).arek1357 pisze: \(\displaystyle{ 11,12,\red 13,14,15 \black ,21,22,\red 23,24,25 \black ,31,41,51}\)