# Ternary strings (combinatorics, recurrence)

The questions is: for $A_n$ find all ternary strings of length $n ≥ 0$ that don't include substring $”11”$. Provide answer in form of:

a) recurrence relation
b) combinatorial expression

After that, for $B_n$ take $A_n$ and exclude strings that also have substring $”12”$ and end with $”1”$ (at the same time).

The biggest issue for me comes with combinatorial expression, whatever I try I cannot include all variations and get kind of lost. Might appreciate a bit of help on recurrence relation as well.

• Alright, I have figured out recurrence relations... Can anyone help with combinatorics? – N. Vinogradov Dec 13 '15 at 23:16

Know this is old, but this is an interesting problem! Let A be a ternary string of length $n$ which does not include the substring $11$. If A does not end in a $1$, then A can be broken up into a unique sequence of the atomic strings $0$, $2$, $10$ and $12$; each $1$ must be followed by a $0$ or $2$, and any remaining characters are either $0$ or $2$. Conversely any string of length $n$ comprised of these atomic strings meets our conditions.
To count the number of such strings of length $n$, let $i$ be the number of length 2 atoms ($10$ and $12$) in the string. The total number of strings of length $n$ using $i$ length 2 atoms from our set is ${{n-i}\choose{i}}2^{n-i}$. To see this, note that we need $i$ length 2 atoms and $n-2i$ length 1 atoms to create a string of length $n$, so a total of $n-i$ atoms. From the $n-i$ available positions in the string, we pick $i$ positions to get length 2 atoms, and once they are picked, there are $2^i$ ways to fill in length 2 atoms. The remaining $n-2i$ positions are filled with length 1 atoms, which can be done in $2^{n-2i}$ ways.
So the total number of length $n$ strings not ending in a $1$ with no $11$ substring is $\sum\limits_{i=0}^{\lfloor\frac{n}{2}\rfloor}{{n-i}\choose{i}}2^{n-i}$.
The number of such strings that do end in a $1$ is calculated similarly, noting that such a string is comprised of a string of length $n-1$ with no $11$ substring that does not end in a $1$, followed by a $1$. Hence there are $\sum\limits_{i=0}^{\lfloor\frac{n-1}{2}\rfloor}{{n-1-i}\choose{i}}2^{n-1-i}$ such strings.
Thus $A_n = \sum\limits_{i=0}^{\lfloor\frac{n}{2}\rfloor}{{n-i}\choose{i}}2^{n-i} + \sum\limits_{i=0}^{\lfloor\frac{n-1}{2}\rfloor}{{n-1-i}\choose{i}}2^{n-1-i}$.