Counting Palindromes of Length n in Base b

 (Notice: Due to recent health problems it has been difficult for me to continue with my blog. I still intend to write future posts as I am able, while also working on my new book series in the background. As a sign of good faith here is an excerpt from the first volume.)

A palindrome is defined in this essay to be any finite sequence $(a_1, a_2, \ ... \ , a_n)$ such that

\[ (a_1, a_2, \ ... \ , a_n) = (a_n, a_{n-1}, \ ... \ , a_1) \ . \]

It is assumed that every element of the palindrome belongs to some finite set of elements $A$. This can be thought of abstractly as the set of letters in a given alphabet, or we can also think of it as the set of symbols in a given integer base. Preferring the latter abstraction, we may then expound further concerning some fixed $n$ and each combination of symbols for this particular length. The set of palindromes of length $n$ is therefore a subset of the Cartesian power $A^n$. By defining the number of elements of $A$ to be $|A| = b$ we may begin our counting exercise.

     We can make the problem more approachable by first separating it into odd and even instances of $n$. Let us begin with the even length palindromes since they are slightly easier to solve. They can be constructed in one of two ways: firstly, by concatenating shorter palindromes of length $n/2$ with themselves; and secondly, by concatenating a non-palindrome of said length with its reverse form. The first way gives us the same number of combinations as there are palindromes of length $n/2$. We can denote this with the palindromic coefficient $P(n/2,b)$. As for the second way, there are two possible arrangements of the shorter non-palindromes: one in which the non-palindrome is concatenated with its reverse on the left-hand side; and one where it is concatenated on the right-hand side. Therefore according to the second method we have $2(b^{n/2} - P(n/2,b))$ possible combinations, because we must subtract the number of shorter palindromes from the total number of sequences of length $n/2$ to find the number of non-palindromes. By combining the two formulas we get the recurrence relation

\[ P(n,b) = P(n/2,b) + 2(b^{n/2} - P(n/2,b)) \]

which then simplifies to

\[ P(n,b) = 2b^{n/2} - P(n/2,b) \ . \]

     This accounts for the even case, now let us turn our attention to the odd length palindromes. The same principles of construction for the even length palindromes can be applied here with the added understanding that we have a middle element to account for as well. Because we can insert any element of $A$ into the middle of our odd length palindrome, there are $b$ possible combinations for each even palindrome of length $n-1$. The number of odd palindromes is therefore

\[ P(n,b) = b(2b^{(n-1)/2} - P((n-1)/2,b)) \ , \]

which can be written as a piece-wise relation using the previous expression 

\[ P(n,b) = \begin{cases} 2b^{n/2} - P(n/2,b), & n \ \text{even} \\ b(2b^{(n-1)/2} - P((n-1)/2,b)), & n \ \text{odd} \end{cases} \ . \]

To implement our formula is not as straightforward as it seems. We do not have a typical additive recurrence relation, such as $a_{n+1} = R(a_n)$, instead we have $a_n = R(a_{\lfloor n/2 \rfloor})$. In order to construct meaningful algebraic expressions from this type of recurrence relation we must resort to an algorithmic decomposition based on some fixed $n$. Let us consider for example $n=11$. The recursive sequence of operations then follows

\[ P(11,b) = b(2b^5 - P(5,b)) \ , \]

\[ P(5,b) = b(2b^2 - P(2,b)) \ , \]

\[ P(2,b) = b \ . \]

By combining these equations we are left with the result

\[ P(11,b) = b(2b^5 - b(2b^2 - b)) \]

which reduces to

\[ P(11,b) = b^3(2b^3 - 2b + 1) \ . \]

We will refer to this as the $n$-th palindromial $p_n(b)$. Therefore, each fixed length $n \geq 1$ has a closed polynomial expression associated with it which counts the number of such palindromes over our set $A$. The first few palindromials are: $p_1(b) = b$, $p_2(b) = b$, $p_3(b) = b^2$, etc.

     As a final note, it would prove interesting to generalize the aforementioned palindromic coefficients to arbitrary dimensions. For instance, the set of symmetric matrices could be viewed as two-dimensional palindromes. The analogy can be extended further to $d$-dimensional cubic arrays that remain unchanged when their elements are reflected through a fixed $(d-1)$-hyperplane. It is left as a challenge for the reader to derive a recursive formula regarding the two-dimensional case.

TMDR Vol. I - Ch. 1 by JRWheat on Scribd