Solving combinatorical problem using characteristic polynomial

Question

How many $6$ length strings above $\left\{1,2,3,4\right\}$ are there such that $24$ and $42$ aren't allowed.

The suitable recurrence relation for this problem is: $a_{n+2} = 2a_{n-1} + 4a{n-2}$. Hence, the characteristic polynomial is: $x^2 -2x -4 = 0$.It's roots are: $1+\sqrt5,1-\sqrt5$.

So, the genral function is: $\alpha (1+\sqrt5)^n + \beta (1-\sqrt5)^n$ We know that: $a_0=1$ and $a_1=4$. Hence,

$\beta = \frac{1}{2} - \frac{3}{2\sqrt5}$, $\alpha = \frac{1}{2} + \frac{3}{2\sqrt5}$

All in all,
$$(\frac{1}{2} + \frac{3}{2\sqrt5})(1+\sqrt5)^n + (\frac{1}{2} - \frac{3}{2\sqrt5})(1-\sqrt5)^n$$

Now, for $n=6$ the result is $1344$, but the book says $1216$.

Who's right?

Answer 1

Let $a_n$ be the number of strings of length n, $b_n$ be the number of strings of length n starting with 1 or 3, $c_n$ be the number of strings of length n starting with 2, and $d_n$ be the number of strings of length n starting with 4.

Then $a_n=b_n+c_n+d_n$, $b_n=2a_{n-1}$, $c_n=b_{n-1}+c_{n-1}$, and $d_n=b_{n-1}+d_{n-1}$.

Substituting the last 3 equations into the first equation gives

$a_n=2a_{n-1}+2b_{n-1}+c_{n-1}+d_{n-1}=2a_{n-1}+b_{n-1}+(b_{n-1}+c_{n-1}+d_{n-1})=2a_{n-1}+2a_{n-2}+a_{n-1}$,

so $a_n=3a_{n-1}+2a_{n-2}$.

Starting with $a_0=1$ and $a_1=4$, we can substitute into this recurrence relation to get

$a_2=14$, $a_3=50$, $a_4=178$, $a_5=634$, and $a_6=2258$.

Answer 2

We may solve such kind of problems using directed graph/finite automaton.

Consider the following graph:

\begin{align*} A = \left[\begin{array}{rrrrrrr} & \mathrm{I} & \mathrm{O} & \mathrm{2} & \mathrm{4} & \mathrm{24} & \mathrm{42}\\ \mathrm{I} & 0 & 2 & 1 & 1 & 0 & 0 \\ \mathrm{O} & 0 & 2 & 1 & 1 & 0 & 0 \\ \mathrm{2} & 0 & 2 & 1 & 0 & 1 & 0 \\ \mathrm{4} & 0 & 2 & 0 & 1 & 0 & 1 \\ \mathrm{24} & 0 & 0 & 0 & 0 & 0 & 0 \\ \mathrm{42} & 0 & 0 & 0 & 0 & 0 & 0 \end{array}\right] \end{align*}

We can now obtain the generating functions for all entries by computing:

$$\left(I-x\, A\right)^{-1}$$

and the g.f. we require is the sum of first four columns in the first row of the inverted matrix, which turns out to be:

\begin{align*} G(x) &= \dfrac{1+x}{1-2\, x-3\, x^2} \\ &= \dfrac{1}{4}\left(\dfrac{1+\dfrac{1}{\sqrt{17}}}{\dfrac{\sqrt{17}-3}{4}-x}-\dfrac{1-\dfrac{1}{\sqrt{17}}}{\dfrac{\sqrt{17}+3}{4}+x}\right) \end{align*}

Extracting $[x^n]$ from the above gives us:

\begin{align*} a_n &= \dfrac{1}{4}\left(\dfrac{1+\dfrac{1}{\sqrt{17}}}{\left(\dfrac{\sqrt{17}-3}{4}\right)^{n+1}}-(-1)^n\, \dfrac{1-\dfrac{1}{\sqrt{17}}}{\left(\dfrac{\sqrt{17}+3}{4}\right)^{n+1}}\right) \\ &\sim \dfrac{1}{4}\, \dfrac{1+\dfrac{1}{\sqrt{17}}}{\left(\dfrac{\sqrt{17}-3}{4}\right)^{n+1}} \end{align*}

and the required answer is $a_6 = 2258$