A string of length $N$ can be made from $6$ characters $a$, $b$, $c$, $d$, $e$ and $f$. There are some rules to make such a string:
$b$ can not come directly after $a$.
$d$ can not come directly after $a$ or $f$
$c$ can not come directly after $c$ or $e$
The string is a palindrome.
How many strings of length $N$ can be made given such constraints?
For $N=1$, there are $6$ such strings: $a$, $b$, $c$, $d$, $e$ and $f$.
For $N=2$, there are $5$ such strings: $aa$, $bb$, $dd$, $ee$ and $ff$.
For $N=3$, there are $27$ such strings: $aaa$, $aca$, $aea$, $afa$, $bab$, $bbb$, $bcb$, $bdb$, $beb$, $bfb$, $cac$, $cbc$, $cdc$, $dbd$, $dcd$, $ddd$, $ded$, $eae$, $ebe$, $ede$, $eee$, $efe$, $faf$, $fbf$, $fcf$, $fef$ and $fff$.
Letting $r=\lceil n/2 -1 \rceil$, we have $$f(n)=\begin{cases} \frac{2^{-r-1}}{\sqrt{17}} \left(\left(5 \sqrt{17}-21\right) \left(5-\sqrt{17}\right)^r+\left(21+5 \sqrt{17}\right) \left(5+\sqrt{17}\right)^r\right) & n \textrm{ even;}\\ \frac{3\ 2^{-r}}{\sqrt{17}} \left(\left(\sqrt{17}-4\right) \left(5-\sqrt{17}\right)^r+\left(4+\sqrt{17}\right) \left(5+\sqrt{17}\right)^r\right) & n \textrm{ odd.} \end{cases}$$
This gives the sequence of values ${1, 6, 5, 27, 23, 123, 105, 561, 479, 2559, 2185\ldots}$ for $n\ge 0$.
To obtain this, define the $6\times6$ transition matrix $M$ to be $(m_{ij})$, with rows and columns labeled by the symbols a,$\ldots$, f, with $m_{ij}=1$ iff symbol $i$ can be followed by symbol $j$. Since the string must be a palindrome, this matrix is symmetric: $$M=\left( \begin{array}{cccccc} 1 & 0 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 1 & 1 \\ \end{array} \right)$$
Define a string to be legal if it respects the transitions; the $ij$ entry of $M^r$ is the number of legal strings of length $r+1$. Now, a palindromic string of length $n$ corresponds precisely to a legal string of length $\lceil n/2\rceil = (n+1)/2$ if $n$ is odd. If $n$ is even, a palindromic string of length $n$ corresponds to a legal string of length $n/2$ which ends in a symbol which can be followed by itself (i.e. any symbol but "c"). Therefore, if we define the vectors $\textbf{j}=(1,\ldots,1)$, and $\textbf{k}=(1,1,0,1,1,1)$, we have $$f(n)=\begin{cases} \textbf{j} M^r \textbf{j}^T, & n \textrm{ even;}\\ \textbf{j} M^r \textbf{k}^T, & n \textrm{ odd,} \end{cases}$$ where $r=\lceil n/2\rceil -1$.
This is an effective formula, but we can get a closed form by diagonalizing $M$. That is, the eigenvalues of $M$ are distinct, so $M=U^{-1}D U$ where $D$ is the diagonal matrix whose entries are the eigenvalues. Thus $M^r=U^{-1}D^r U$, which leads to the closed form claimed.