Sequence of 0s and 1s containing no two 0s or three 1s in a row

Question

How many sequences of 0s and 1s of length 19 are there that contain no two consecutive 0s, and contain no three consecutive 1s?

This is different from the one posted here Place 1s and 0s

Note "How many sequences of 0s and 1s of length 19 are there that contain no three consecutive 1s?" is much easier. My question additionally does not allow two 0s in a row.

Answer 1

For each positive integer $n$,

• Let $f(n)$ be the number of qualifying sequences of length $n$.$\\[4pt]$
• Let $a(n)$ be the number of qualifying sequences of length $n$ with first term equal to $0$.$\\[4pt]$
• Let $b(n)$ be the number of qualifying sequences of length $n$ with first term equal to $1$.$\\[4pt]$

Clearly we have $f(n)=a(n)+b(n)$.

Our goal is to find $f(19)$.

The functions $a,b$ satisfy the linked recursion
\begin{align*} a(n)&= \begin{cases} 1&\text{if}\;n=1\\ b(n-1)&\text{if}\;n > 1\\ \end{cases} \\[8pt] b(n)&= \begin{cases} 1& \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \text{if}\;n=1\\ 2& \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \text{if}\;n=2\\ a(n-1)+a(n-2)&\text{if}\;n > 2\\ \end{cases} \\[4pt] \end{align*} Applying the recursion, we get \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline n&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19\\ \hline a(n)&1&1&2&2&3&4&5&7&9&12&16&21&28&37&49&65&86&114&151\\ \hline b(n)&1&2&2&3&4&5&7&9&12&16&21&28&37&49&65&86&114&151&200\\ \hline f(n)&2&3&4&5&7&9&12&16&21&28&37&49&65&86&114&151&200&265&351\\ \hline \end{array} hence $f(19)=351$.