How many different possibilities are there? I was doing this cool real life puzzle game in Shanghai, China. It works like this:

You and a group of friends are locked in a room together - no smartphones, no cameras - and your task is to get out. One of the questions was a number puzzle to unlock a digital keypad.
Here is what it said:
The code contains only these numbers (but must use them all) $4, 6, 9$
It is a $6$ digit code.
The code ends in $4$.
$4$ and $9$ are never consecutive.

The correct answer was $4,6,6,9,6,4$.
I feel I just got lucky at getting the code correct. So my question is this:

How many different possibilities are there?

Thanks.
 A: Let $N_{a,b}$ be the codes of length $a$ that end in $b$ and have no adjacent $4$'s and $9$'s.  Each code of length $a$ that ends with $b$ can be extended uniquely to a code of length $a+1$ that ends in $c$, unless $(b,c)=(4,9)$ or $(9,4)$.  So
$$
N_{a+1,4}=N_{a,4}+N_{a,6} \\
N_{a+1,6}=N_{a,4}+N_{a,6}+N_{a,9} \\
N_{a+1,9}=N_{a,6}+N_{a,9},
$$
or
$$
N_{a+1}=\left(\begin{array}{ccc}1 & 1 & 0\\1 & 1 & 1\\0 & 1 & 1\end{array}\right)\cdot N_{a}
$$
in a matrix notation, where $N_{0}=(1,1,1)^{t}$.  One finds that $N_6=(169,239,169)^t$, so there are $169$ six-number codes ending with a $4$.  We need to subtract the codes of this type that don't use all three numbers… since $4$'s and $9$'s can't be adjacent, these are just those codes containing $4$'s and $6$'s only, of which there are $2^5=32$ ending in $4$.  The result is $169-32=137$.
A: Let $a_n$, $b_n$, and $c_n$ be the number of n-digit codes that end in a 4, 9, or 6, respectively, without the requirement that all 3 digits are used.
If $e_n$ gives the total number of n-digit codes, then
$a_n=e_{n-1}-b_{n-1}$, $b_n=e_{n-1}-a_{n-1}$, and $c_n=e_{n-1}$ and
$e_n=a_n+b_n+c_n=3e_{n-1}-(a_{n-1}+b_{n-1})=3e_{n-1}-(e_{n-1}-c_{n-1})=2e_{n-1}+e_{n-2}$; 
so $e_1=3, e_2=7, e_3=17, e_4=41, e_5=99$.
Since $a_n=b_n$ by symmetry, $e_n=2a_n+e_{n-1}\;\;$and therefore $a_n=\frac{1}{2}(e_n-e_{n-1})=\frac{1}{2}(e_{n-1}+e_{n-2})$.
Then $a_6=\frac{1}{2}(e_5+e_4)=70$, and 
we must deduct the number of 6-digit codes ending in 4 which do not include a 9.
Since there are $2^5$ such codes, there are $70-2^5=70-32=38$ possibilities.
$-----------------------------------$
An alternate way to count the number of possibilities is to break this up into cases, based on the number $\;\;l$ of consecutive 4's at the end of the code.
Then $1\le l\le4$, and the digit preceding the string of 4's must be a 6; so
there are $\displaystyle\sum_{m=1}^4 (e_m-2^m)=1+3+9+25=38$ possibilities. (where $m=5-l$) 
