Matematické Fórum

godzila · 20. 12. 2015 12:36

Zdravím,
mám příklad a potřeboval bych trochu popostrčit.

Ternárním slovem délky n ≥ 0 rozumíme libovolné $x\in \{0,1,2\}^n$ (Řetězec kde na každé pozici může být 0 nebo 1 nebo 2 o délce n)
Zaveďme následující množiny:
1. An obsahuje všechna slova z $\{0,1,2\}^n$ , které neobsahují faktor (podřetězec) ”11”.
2. Bn obsahuje všechna slova z An, které navíc neobsahují ani faktor ”12” a nekončí jedničkou.
3. Cn obsahuje všechna slova z $\{0,1,2\}^n$ , které neobsahují po sobě jdoucí nenulové cifry.
Kombinatorickou úvahou odvoďte nerekurentní předpis pro mohutnosti an = |An|, bn = |Bn| a
cn = |Cn| (přípustný výsledek může obsahovat sumy, kombinační čísla a mocniny a závisí pouze
na n).

1. Příklad nejspíš mám, vychází mi $a_n=3^n-\sum_{i=1}^{n-i}\binom{n-i}{1}$
Kde $3^n$ je celkový počet kombinací všech řetězců a odečítám podřetězce "11"
U 2. příkladu ale nevím snažím se odečíst podřetězce "12" a řetězce končící na 1 a potom přičíst řetězce končící na "11" protože jsem je odečetl 2x ale nevím jak na to

Matematické Fórum

#1 20. 12. 2015 12:36

Kombinace řetězců

Zápatí