Matematické Fórum

ZADÁNÍ:
Označme množinu všech ternárních řetězců délky n, které neobsahují faktor (podřetězec)
"22", jako An. Dále nechť Bn značí množinu všech takových řetězců, které neobsahují ani
faktor "21" a navíc nekončí dvojkou.
Určete kolik nejvýše dvojek mohou obsahovat řetězce z An a řetězce z Bn.
Kombinatorickou úvahou pak odvoďte nerekurentní předpis pro velikosti an = |An| a
bn = |Bn|

vysvětlení + moje řešení:
ternární množina {0,1,2}

moje řešení pro první polovinu:
An 2x2x2x2x2... -> Horní celá část
Bn 2020202020... -> Dolní celá část

druhá polovina:
Dospěla jsem k tomuhle prozatim:
pro An  - (rozložení na možnosti znaků na určitém indexu)
Lze představit jako strom:
pro n=1 -> 3 {0,1,2}
pro n=2 -> 8 {(první místo 3, druhé místo 3) - tam kde jsou 2 dvojky (1 případ) nebolli 3,2,3}
pro n=3 -> 22 {3 -> 3,2,3 ; 2-> 3,3 ; 3-> 3,2,3}
pro n=4 -> 60 {3 -> 3,2,3 ; 2-> 3,3 ; 3-> 3,2,3....}
pro n=5 -> 164...
pro n=6 -> 448..
pro n=7 ->1224..

pro rozepsání, jsem přišla úvahou na to, že např u
A5 = (A4+A3)osmiček "[počtu osmiček, neboli 3,2,3]" x2
+
A5 = (A4+A3)šestek "[počtu šestek, neboli 3,3]" x2
= těch 164, to je ale rekurentně a nedotažené...
Věděl by někdo jak to bude nerekuretně a dobře? :)