Palindrome with odd sum

Question

I believe the number of palindromes that do not include 0 and sum to even $n$, such as $1+1+2+1+1=6$, is equal to $2^{n/2}$. I think this because if we consider the first half of the palindrome:

• if the palindrome is even-length, we can either apply stars-and-bars for a sum over the number of bars like $\binom 2 0 + \binom 2 1 + \binom 2 2$, or consider binary choices of whether to include a divider/bar of the $n/2 - 1$ bars. This gives us $2^{n/2-1}$ even-length palindromes
• every odd-length palindrome has a value that spans the halfway point of the palindrome, like $1+4+1 = 1+2+2+1$, and corresponds to an even-length palindrome

So the number of palindromes is $2 \times 2^{n/2-1} = 2^{n/2}$.

First I would like to verify if this reasoning is correct and if there is a simpler interpretation. Maybe the bars can be placed directly without appealing to splitting the palindrome in half? My main question is on how to apply this logic of spanning the halfway point for odd-sum palindromes, like $1,3,1$. If we try to divide the palindrome evenly in half we get a sum like $1 + 1.5 + 1.5 + 1$. I think the same logic of considering the first half of the palindrome applies, but we also consider the middle digit, that is $\displaystyle\frac{n+1}{2}$ digits?

Answer 1

I found out from A016116 these are called symmetric compositions of $n$. My logic applies to even and odd sums based on placing dividers, for example $n=5$:

$$1\ |\ 1\ |\ 1 \ |\ 1\ |\ 1$$

Choosing whether or not to place the first two dividers (or replacing them with $+$) determines the last two, so there are $2^2=4$ palindromes.

Answer 2

Unfortunately your initial reasoning for the number of even-length palindromes only works for sums $\le$ 18; once the sum goes higher, the stars-and-bars approach would allow for parts of size larger than 9, which won't work as we need to partition the sum into digits.

For a similar reason, the number of odd-length palindromes will not be equal to the number of even-length ones. You are right that every palindrome of odd length $m$ can be associated to one of even length $m+1$; but the association, while it is 1-to-1, is not onto, i.e. there will be palindromes of even length that don't associate with any of odd length. If the two central digits of a palindrome of even length $m+1$ are $\ge$ 5 (e.g. 1,6,6,1) it cannot associate with a palindrome of odd length $m$ as the central 'digit' would be too large.

In order to calculate the number of palindromes with even sum $2n$, we need a formula for the number of $k$-compositions of $n$ - which are ordered partitions of the integer $n$ into $k$ parts - with the restriction that each part be an integer between 1 and 9. On page 441 of this paper, part (E) gives such a formula, but there is no indication of how it was derived.

Using a slightly simplified version of their notation,

$$F(n,k;1,9) = \sum_{j=0}^{k} (-1)^j \binom{k}{j} \binom{n-9j-1}{k-1}$$

Let $E_i, O_i$ and $P_i$ represent, respectively, the number of even-length, odd-length and total palindromes with sum $i$.

Then the number of even-length palindromes with even sum $2n$ would be

$$E_{2n} = \sum_{k=1}^{n} F(n,k;1,9) = \large\sum_{k=1}^{n} \normalsize\left[ \sum_{j=0}^{k} (-1)^j \binom{k}{j} \binom{n-9j-1}{k-1} \right]$$

In an odd-length palindrome with even sum, the central digit would have to be either 2, 4, 6 or 8. Then the number of odd-length palindromes with even sum $2n$ would be

$$O_{2n} = E_{2n-2} + E_{2n-4} + E_{2n-6} + E_{2n-8}$$

and therefore the total number of palindromes with even sum $2n$ would be given by

$$\begin{align} P_{2n} &= E_{2n} + O_{2n} \\ &= E_{2n} + E_{2n-2} + E_{2n-4} + E_{2n-6} + E_{2n-8} \end{align}$$

A palindrome with odd sum would have to have an odd number of digits and have 1, 3, 5, 7 or 9 as its central digit; thus the number of palindromes with odd sum $2n+1$ would also be given by

$$P_{2n+1} = E_{2n} + E_{2n-2} + E_{2n-4} + E_{2n-6} + E_{2n-8}$$

In other words,

$$P_{2n+1} = P_{2n}$$