Tiles Combinatorics I have the following question:
Let there be a road of length $n$.
there are 3 types of tiles: of lengths 1,2,3.
We'll define  $a(n)$ as the number of roads of $n$ tiles where a tile of length 1 and a tile of length 2 can not be adjacent.
I need to find a recurrence relation for $a(n)$.
I've manually calculated $a(n)$ for $0\leq n \leq6$ and I got $a(0)=1, a(1)=1, a(2)=2, a(3)=2, a(4)=4, a(5)=6, a(6)=9$, but I can't find the general relation.
Thanks for the help.

disclaimer This is too long to be a comment and can be viewed as a partial answer; as I can't finish it yet, but it may help someone else, I provide with what I have so far.
Let me define 3 sequences with easier to find recurrence relations:
$u(n) $ gives the number of roads of length $n $ that end with a tile of length $1$;
$d(n) $ gives the number of roads of length $n $ that end with a tile of length $2$;
$t(n) $ gives the number of roads of length $n $ that end with a tile of length  $3$.
All those roads are restricted to the condition imposed by the OP: no 1-tile is adjacent to a 2-tile.
The following should be immediate:
$$a(n) = u(n) + d(n) + t(n)\\
u(n) = u(n-1) + t(n-1)\\
d(n) = d(n-2) + t(n-2)\\
t(n) = u(n-3) + d(n-3) + t(n-3) $$
Also we have that $u,d,t$ are $0$ if $n <0$ and $u(0) = d(0) = t(0) = 1$ just so the relations work fine from the get go.
