I am preparing for my finals for discrete mathematics and I came across this exercise in textbook.
Let $s_{n}$ denote all ternary strings of length $n$, such that any string in $s_{n}$ does not contain substring $00$, $01$ and the last symbol is not $0$. Find:
-
non recurrent sum for $s_{n}$ using combinatorics
-
recurrence relation $s_{n}$.
I managed to find recurrence relation ${s}'_{n} = 2s_{n-1} + s_{n-2}$ that satisfies the first two conditions (no $00$'s and $01$'s) but I have no idea how to find RR with all three conditions. My first thought was to make some correction in initial conditions, but after trying it I got even more confused.
As for the sum, I'm lost as well.
Can you point me in the right direction towards solution?
Best Answer
Observe that the conditions you are given are equivalent to the single condition that "every $0$ must be immediately followed by a $2$." In particular, this means that any such sequence of length $n$ is either (a) such a sequence of length $n-1$ with a $1$ or $2$ appended to the end, of which there are $2s_{n-1}$, or (b) such a sequence of length $n-2$ with a $02$ appended to the end, of which there are $s_{n-2}$. (Also note that these cases are mutually exclusive since strings from the first case can't have a $0$ as the second-to-last symbol.) This gives your recurrence $s_n = 2s_{n-1} + s_{n-2}$. For the initial conditions, you get $s_1 = 2$ and $s_2 = 5$ (just count these by hand).
You can use the same equivalent condition above to write a combinatorial sum. You can think of this as an unrestricted string with three different symbols: $a=1$, $b=2$, and $c=02$, where the third symbol $c$ takes up two spots. If there are $k$ copies of the symbol $c$ in a string of length $n$, then there must be a total of $n-k$ symbols $a, b, c$. Try to write an expression for the number of such strings with $k$ copies of $c$, and then sum over all possible values of $k$ for your answer. (Since this is homework, I'll let you take it from here.)