Suppose we have $n$ slots to fill with words from a regular alphabet of $26$ letters. We would like to find all possible palindromes of length less than or equal to $n$, where the minimum palindrome is of length $3$ (e.g. aba). We know that for the case where $n=3$ there are $26^2$ ways to construct such a palindrome. For $n=4$ there are $(26^2)$ palindromes, all of which are of length $4$ since having a sub-palindrome of length $3$ would result in the total $4$-slot word being non-palindromic. For the case where $n=5$ we have three degrees of freedom and $26$ additional 'bonus cases' where we have that the outer two characters are equal to the inner two characters, resulting in two sub-palindromes. As a finally example, skipping $n=6$ we have the case $n=7$ where the maximal palindromes are of the form abcdcba, where if $c=a$ or $d=a$, for example, we get additional sub-palindromes to add to our count.
Example: $n=5$:
abcba means that we have $26^3$ possible palindromes + $3(26^2)$ since we can either fix $c=a$ or $a=b$ or $b=c$
I am looking to generalize this to find all possible palindromes of length less than or equal to $n$ for arbitrary $n$. I have noticed that The number of degrees of freedom increases every two palindromes, only increasing at odd $n$ (since there is a unique median letter for these cases), and that there are restrictions on the number of shifts for each $k\leq n$ that depend on $n$ but I am not sure how to use these facts or whether they are inherently useful. Any input is appreciated.
Best Answer
The easiest method is to simply count palindromes of length exactly n. For even n, this is $26^{n/2}$, and for odd n, $26^{(n-1)/2}$.
So, if we include lengths 1 and 2, we want to add $26 +26 +26^2 +26^2 + 26^3 + 26^3 + \ldots$
If n is even, this is just twice the sum of a geometric series. If n is odd, you get one extra term to add at the end. (You can subtract the 52 sequences of length <= 2 at the end if you like).