Find a recurrence relation for the number of ternary strings of length n that after 1 there is no 0 nor 2.
Don't know how to approach these kinds of problems.
Asked
Active
Viewed 154 times
0
-
Hint: the pattern for such strings is $W1^k$ where $W$ is any string (of length $n-k$) in just $0,2$. – lulu Dec 16 '16 at 22:43
1 Answers
0
HINT: Let $S_n$ be the set of such strings of length $n$. Notice that if $\sigma=s_1\ldots s_n\in S_n$, and there is a $k$ such that $s_k=1$, then $s_i=1$ for $k\le i\le n$. That is, if a string in $S_n$ has a $1$, every element after that $1$ must also be a $1$.
- How many ternary strings of length $n$ have no $1$s?
- More generally, if $0\le k\le n$, how many ternary strings of length $n$ end in exactly $k$ $1$s and have only $0$s and $2$s before those $1$s?
Every member of $S_n$ must be of the kind described in the last bullet point.
Brian M. Scott
- 616,228