Matematické Fórum

PierreLaplace · 20. 01. 2018 17:18

Zdravím, chtěl bych se zeptat, zda byste nevěděli jak řešit tuto úlohu. Děkuji.

Nechť Sn je počet binárních řetězců délky n ∈ N+ , které neobsahují podřetězec 01.
Odvoďte vhodný rekurentní vztah pro posloupnost Sn.

Jj · 21. 03. 2018 17:38

Téma už je zřejmě dávno "mrtvé", jen mě teď napadlo, že k rekurentnímu vztahu lze jednoduše dojít výpisem řetězců délky n = 1, 2, 3, ..., které podřetězec "01" neobsahují:

Code:

n   Sn    výpis
----------------------------------------------------
1   2     0    1
2   3     00   10   11
3   4     000   100   110   111
4   5     0000   1000   1100   1110   1111
5   6     00000   10000   11000  11100  11110   11111

. . .

Řekl bych, že ostatní neuvedené řetězce dané délky podřetězec "01" nutně obsahují.

Takže rekurentní vztah by zřejmě mohl být $S_{n+1}=S_n+1,\; S_1=2$

Nebo se pletu?

jarrro · 21. 03. 2018 19:30 — Editoval jarrro (10. 09. 2021 06:27)

↑ Jj:podľa mňa ok, ale chcelo by to odvodenie napríklad by samohli "dobré" reťazce rozdeliť na tie čo končia nulou (nech ich je $S_{0,n}$ ) a na tie čo končia jednotkou (nech ich je $S_{1,n}$ )
Zrejme $S_{0,1}=1, S_{1,1}=1$
Nulou môžeme rozšíriť každý "dobrý" reťazec a jednotkou len ten čo končí jednotkou preto
[mathjax]\begin{align}S_{0,n+1} &= S_{0,n}+S_{1,n}\\
S_{1,n+1} &= S_{1,n}
\end{align}[/mathjax]
Z $$2$$ dostávame
$S_{1,n}=1$
sčítaním $$1$$ a $$2$$ dostávame
$S_{n+1}=S_{0_n+1}+S_{1,n+1}=S_{0,n}+S_{1,n}+S_{1,n}=S_n+1$