Number of sequences of length $m$ such that $1$ is never followed immediately by $0$

Question

Find the number of sequences of length $m$ consisting of only digits, where each digit is in $\{0,1,2\}$ and such that $1$ is never followed immediately by $0$.

Attempt: I tried taking 10 as a block, but I got nowhere. I found the Mathematics question Number of permutations of thet set $\{1,2,...,n\}$ in which $k$ is never followed immediately by $k+1$.

Using that, since I need to remove only 1 followed by 0, I get only one set $A_1$ so, $3^m$ - 6 (3*2). Pick the other number in three ways, and we can permute 10 and other number in two ways). Is this right? I am from a non-math background; kindly consider this if possible.

Answer 1

HINT: Call such sequence good, and let $a_n$ be the number of good sequences of length $n$. If $\sigma$ is a good sequence of length $n$, we can form $3a_n$ sequences of length $n+1$ by appending a $0,1$, or $2$ to the end of $\sigma$. Every good sequence of length $n+1$ can be obtained in this way, but unfortunately so can some bad ones. The bad ones are those that end in $10$. These are clearly obtained by appending $01$ to a good sequence of length $n-1$, and there are $a_{n-1}$ of those, so our count of $3a_n$ includes exactly $a_{n-1}$ bad sequences, and we find that $a_{n+1}=3a_n-a_{n-1}$, or

$$a_n=3a_{n-1}-a_{n-2}\tag{1}$$

with initial values $a_0=1$ (because the empty sequence is good) and $a_1=3$.

Now use your favorite method to solve the recurrence $(1)$ to get a closed form for $a_n$.

A Shortcut: If you calculate the first few $a_n$, you get the following table:

$$\begin{array}{rcc} n:&0&1&2&3&4&5&6\\ a_n:&1&3&8&21&55&144&377 \end{array}$$

If you recognize the bottom row as a subsequence of some familiar sequence, you may be able to prove that it really is that subsequence and use that to get a closed form more easily.

Added: Since Jack D’Aurizio has now mentioned the Fibonacci numbers explicitly, I’ll elaborate on the shortcut bit. It’s quite well known (and easy to show) that the number of ways to tile a $1\times n$ strip using $1\times 1$ and $1\times 2$ tiles (monominoes and dominoes) is $F_{n+1}$. Thus, there are $F_{2n+2}$ ways to tile a strip of length $2n+1$. Number the cells of the strip $1$ through $2n+1$ from left to right, and suppose that we have a tiling of the strip by monominoes and dominoes. Label each even-numbered cell $L$ if it’s covered by the left half of a domino, $R$ if it’s covered by the right half of a domino, and $S$ if it’s covered by a monomino. There are $n$ even-numbered cells, so this labelling produces a string of length $n$ over the alphabet $\{L,R,S\}$. The only restriction on these strings is that they cannot contain the substring $LR$ (why?). Thus, there are $F_{2n+2}$ strings of length $n$ over the alphabet $\{L,R,S\}$ in which $L$ is never followed by $R$. Replace $L,R$, and $S$ by $1,0$, and $2$, respectively, to map these strings to the ones in the problem.

Answer 2

We may consider a Markov chain with three states $\{0,1,2\}$, corresponding to the last parsed character. The adjacency matrix of such a Markov chain is $$ P=\begin{pmatrix}1 & 0 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1\end{pmatrix} $$ (so just the transition $0\mapsto 1$ is not allowed) and the number $S_m$ of strings of $m\geq 1$ characters with the given property is the sum of the elements of $P^{m-1}$. You may now compute $S_m$ from a spectral decomposition of $P$. The usual combinatorial way is to consider that any valid string with length $m$ may only start with a prefix among $$ 1,\quad 2,\quad 02,\quad 002,\quad 0002,\quad \ldots,\quad 000\ldots000.$$ It follows that, by setting $S_0=1$, $$ S_m = 2 S_{m-1} + S_{m-2} + S_{m-3} + \ldots + S_{0} $$ $$ S_{m+1} = 2 S_{m} + S_{m-1} + S_{m-2} + \ldots + S_{0} $$ $$ S_{m+1}-S_{m} = 2S_m-2S_{m-1}+S_{m-1} $$ and $$ S_{m+1} = 3S_{m}-S_{m-1},\quad S_0=1, S_1=3 $$ so $$\boxed{ S_m = \frac{1}{\sqrt{5}}\left[\left(\frac{3+\sqrt{5}}{2}\right)^{n+1}-\left(\frac{3-\sqrt{5}}{2}\right)^{n+1}\right]=\color{red}{F_{2n+2}} }$$ the number of our strings is given by a Fibonacci number. A combinatorial bijection showing the same can be the following one: if we map $0\mapsto 01$, $1\mapsto 10$, $2\mapsto 00$, the valid strings having length $n$ are mapped into the binary strings of length $2n$ with the property that two "$1$s" are never next to each other. For instance: $$ 021002 \mapsto 010010010100 $$ and the latter problem is a famous problem.

Answer 3

For variety, let $A_n$ be the number of such sequences of length $n$ that end in a $1$.

Let $B_n$ be the number of such sequences of length $n$ that do not end in a $1$.

Then,

• $A_0 = 0$
• $B_0 = 1$
• $A_{n+1} = A_n + B_n$
• $B_{n+1} = A_n + 2 B_n$

You can use your favorite method to solve this recurrence relation.

(phrases for further searching: "linear recurrence", "difference equation")

Answer 4

This answer is based upon the Goulden-Jackson Cluster Method.

We consider the set words of length $m\geq 0$ built from an alphabet $$\mathcal{V}=\{0,1,2\}$$ and the set $B=\{10\}$ of bad words, which are not allowed to be part of the words we are looking for. We derive a generating function $f(s)$ with the coefficient of $s^m$ being the number of searched words of length $m$.

According to the paper (p.7) the generating function $f(s)$ is \begin{align*} f(s)=\frac{1}{1-ds-\text{weight}(\mathcal{C})}\tag{1} \end{align*} with $d=|\mathcal{V}|=3$, the size of the alphabet and $\mathcal{C}$ the weight-numerator of bad words with \begin{align*} \text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[10]) \end{align*} We calculate according to the paper \begin{align*} \text{weight}(\mathcal{C}[10])&=-s^2\\ \end{align*}

and get

\begin{align*} f(s)&=\frac{1}{1-ds-\text{weight}(\mathcal{C})}\\ &=\frac{1}{1-3s+s^2}\\ \end{align*}

Partial fraction decomposition and expansion of $f(s)$ results in

\begin{align*} f(s)&=\frac{3+\sqrt{5}}{2\sqrt{5}}\cdot\frac{1}{1-\frac{3+\sqrt{5}}{2\sqrt{5}}s} -\frac{3-\sqrt{5}}{2\sqrt{5}}\cdot\frac{1}{1-\frac{3-\sqrt{5}}{2\sqrt{5}}s}\\ &\\ &=\frac{1}{\sqrt{5}}\sum_{m=0}^{\infty}\left[\left(\frac{3+\sqrt{5}}{2}\right)^{m+1}-\left(\frac{3-\sqrt{5}}{2}\right)^{m+1}\right]s^m\\ \\ &=1+3s+8s^2+21s^3+\color{blue}{55}s^4+144s^5+377s^6+\cdots \end{align*} with the coefficient of $s^m$ giving the number of valid words of length $m$.

The number of valid words of length $4$ is $55$. Here is a list showing all $4^3=81$ words and the $26$ invalid words marked with blue.

\begin{array}{ccccccccc} 0000&0\color{blue}{10}0&0200&\color{blue}{10}00&1\color{blue}{10}0&1200&2000&2\color{blue}{10}0&2200\\ 0001&0\color{blue}{10}1&0201&\color{blue}{10}01&1\color{blue}{10}1&1201&2001&2\color{blue}{10}1&2201\\ 0002&0\color{blue}{10}2&0202&\color{blue}{10}02&1\color{blue}{10}2&1202&2002&2\color{blue}{10}2&2202\\ 00\color{blue}{10}&01\color{blue}{10}&02\color{blue}{10}&\color{blue}{10}\color{blue}{10}&11\color{blue}{10}&12\color{blue}{10}&20\color{blue}{10}&21\color{blue}{10}&22\color{blue}{10}\\ 0011&0111&0211&\color{blue}{10}11&1111&1211&2011&2111&2211\\ 0012&0112&0212&\color{blue}{10}12&1112&1212&2012&2112&2212\\ 0020&0120&0220&\color{blue}{10}20&1120&1220&2020&2120&2220\\ 0021&0121&0221&\color{blue}{10}21&1121&1221&2021&2121&2221\\ 0022&0122&0222&\color{blue}{10}22&1122&1222&2022&2122&2222\\ \end{array}