Find number of decimal representations with no consecutive $1$ and $2$

Question

Let $a_n$ be the number of decimal numbers with no two consecutive $1$ and $2$.

We may find this number using generating function. But first of all we should write representation of all decimal numbers with consecutive $1$ and $2$ (let it be $b_{n})$, and $a_n = 9\cdot 10^{n-1} - b_{n}$.

We may represent it using $\{0\} , \dots , \{9\}$. So for $b_{n}$ we have sequence $(1\cup \dots \cup 9 \cup \{\emptyset\})(12(0 \cup \dots \cup9)^{*})^{*}$, we may compute generating function corresponding to this sequence. $F(x) = \frac{(1+9x)(1-10x)}{1-10x-x^2}$. Now if we represent it with series we have that $a_{n} = \frac{(454 - 89 \sqrt{26}) (5 + \sqrt{26})^n - (5 - \sqrt{26})^n (454 + 89 \sqrt{26})}{2 \sqrt{26}}$.

First 3 numbers are valid, but for $n = 4$, $a_n = 191$, instead of $279$ (number of $4$-decimal numbers with consecutive $1$ and $2$).

Maybe there is a problem with my sequence-notation?

Answer 1

There's something wrong with your generating function. Let's compute $a(x)=\sum\limits_{n=0}^{\infty}a_n x^n$.

We denote by $D=\{0,1,\ldots,9\}$ the set of digits, and by $A_n\subseteq D^n$ our sets (with $|A_n|=a_n$) of $n$-digit numbers with no consecutive $1$ and $2$, viewed as words of length $n$ over $D$. Clearly, $a_1=9$ (the elements of $A_1$ are one-letter words over $D\setminus\{0\}$); for the following induction step to be correct, we assume that $A_0$ consists of the (single) empty word, so that $a_0=1$. Now, for $a\in D^n$ and $b,c\in D$, we have $abc\in A_{n+2}$ if and only if $ab\in A_{n+1}$ and $bc\neq 12$; note that if $bc=12$ we still have $ab\in A_{n+1}\iff a\in A_n$: $$A_{n+2}=(A_{n+1}\cdot D)\ \setminus\ (A_n\cdot\{12\})\implies a_{n+2}=10a_{n+1}-a_n,$$ which gives $a(x)=\color{blue}{\dfrac{1-x}{1-10x+x^2}}=1+9x+89x^2+881x^3+\underbrace{8721}_{=9000-\color{red}{279}}x^4+86329x^5+\ldots$

Answer 2

I liked metamorphy's explanation.

The same problem can be solved with matrices.

• Let $c_n$ be the number of $n$ digit numbers containing a 1 followed by a 2.
• Let $d_n$ be the number of $n$ digit numbers with a last digit (mod 10) of 1 excluding numbers containing a 1 followed by a 2,
• And let $e_n$ be the number of $n$ digit numbers excluding those that have a 1 followed by a 2 and excluding the numbers that end in a 1.

The numbers you are looking for are $a_n = d_n+e_n= 9\cdot10^n- c_n$, the number of $n$ digit numbers that do not contain a 1 followed by a 2.

These three sequences obey $c_{n+1} = 10 c_n + d_n$, $d_{n+1} = d_n + e_n$, and $e_n = 8 d_n + 9 e_n$, so $$ \left(\begin{matrix} c_{n+1}\\d_{n+1}\\e_{n+1}\end{matrix}\right) = B\left(\begin{matrix} c_n\\d_n\\e_n\end{matrix}\right) $$ where $$B = \left(\begin{matrix} 10 & 1 & 0\\ 0 & 1 & 1\\ 0 & 8 & 9\end{matrix}\right).$$ Now it is pretty easy to compute the sequences with $$ \left(\begin{matrix} c_n\\d_n\\e_n\end{matrix}\right) = B^{n-1} \left(\begin{matrix} 0\\1\\8\end{matrix}\right). $$