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.

  • $\begingroup$ Key words being 'less than or equal to'. $\endgroup$ – user11977 Feb 18 '14 at 19:59
  • $\begingroup$ @John I have edited my post, I shouldn't have had 2 there. $\endgroup$ – 114 Feb 18 '14 at 20:46
  • 1
    $\begingroup$ @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$? $\endgroup$ – 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$

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).

  • $\begingroup$ This solves part of the problem, but will we not have to add in those cases where there are sub-palindromes? For example if n=6 and we write abaaba we have 3 palindromes in only one case. $\endgroup$ – 114 Feb 18 '14 at 20:20
  • $\begingroup$ @Stopwatch: usually one only counts abaaba as one palindrome of length 6. We have already counted aba as one palindrome of length 3. If you want to count differently, you need to specify that. How many would you count in aaaaaa? $\endgroup$ – Ross Millikan Feb 18 '14 at 21:23

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.