# Palindromes of Length Less Than or Equal to N

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.

• Key words being 'less than or equal to'. – user11977 Feb 18 '14 at 19:59
• @John I have edited my post, I shouldn't have had 2 there. – 114 Feb 18 '14 at 20:46
• @Stopwatch I think your question still needs some clarification. Your comment to user11977 below indicates we aren't calculating the answer the same way you are. Can you give the explicit answer for $n=5$ and $n=6$? – John Habert Feb 18 '14 at 20:57

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$
In regards to the accepted answer post of user11977, the formula provided for the number of palindromes is incorrect and for odd $$n$$ is $$\dfrac{26^{n+1}}{2}$$, not $$n-1$$ as posted above on February 2014. The part about $$26^{n/2}$$ is correct for even $$n$$.
To rationalize this, in even $$n$$ scenarios, the first half $$(\dfrac{n}{2})$$ can be anything, while the rest are set based on the configuration of the first half. In odd $$n$$ scenarios, the first $$\dfrac{n+1}{2}$$ characters can be anything, while the rest are set.