# How many combinations can be made from a 10 digit number given these rules?

How many combinations can be made from a 10 digit number given these rules?

Rules:

• you can only use the digits 0, 1 and 2
• the difference between the digits can only be 0 or 1, so you can have 2222222222 or 0000000000 or 0112112100 but not 2011211221 since the difference between the digits should be equal to or less than 1.

Let $f_n$ be the number of combinations obeying those two rules of length n, and let $g_n$ be the number of those that end with $1$, and $h_n$ be the number that end with $0$. Note that $h_n$ is also the number of such combinations that end with $2$ because of the symmetry, so $f_n$ = $g_n + 2 \cdot h_n$.
But $g_n = f_{n-1}$, because I can always add a $1$ to the end of any such combination of length $n-1$ to get a combination of length $n$, and pulling off a $1$ from the end of such a combination of length $n$ still obeys the two rules. To get a length $n$ combination that ends with $0$, though, the preceding combination has to end with a $0$ or a $1$, so $h_n = g_{n-1} + h_{n-1}$. So, we get $$f_n = f_{n-1} + 2 \cdot \left( g_{n-1} + h_{n-1} \right) \\ = 2 \cdot f_{n-1} + g_{n-1} \\ = 2 \cdot f_{n-1} + f_{n-2}$$
• The question didn't ask for a closed form, just for $f_{10}$. From $f_1=3$, $f_2=7$, and the recursion, it shouldn't be too hard to work out $f_{10}$. If you need a closed form, it will involve the roots of $x^2-2x-1$. Apr 1, 2014 at 9:46
• @GerryMyerson You are right, it's $\pmatrix{f_{n-1}\\f_n} = \pmatrix{0&1\\1&2} \pmatrix{f_{n-2}\\f_{n-1}}$, and then your polynomial is of course correct, my bad. Deleted the wrong comments. Apr 1, 2014 at 10:03