<s>[INST] Special Palindromic String 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$.
 [/INST] 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.
</s>