for $A_n$ find all ternary strings of length $n ≥ 0$ that don't include substring $”11”$.

Question

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.

Answer 1

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}$.

Answer 2

I happened to chance on this, so here is the combinatorial approach that you wanted, which is incidentally much simpler !
Hope you like it !

Combinatorial approach

Any string of $i$ non-$1's$ create $(i+1)$ gaps (including ends) where non-adjacent $1's$ can be put,

thus if string length is $n$, the minimum number of non $1's$ needed is $\lfloor\frac{n}2\rfloor$ to ensure that no $1's$ are adjacent.

and in the $(i+1)$ gaps, we just need to fit in the $(n-i)\;\;1's$

$$f(n) = \sum_{i={\lfloor\frac{n}2\rfloor}}^n\binom{i+1}{n-i}$$