While reading in a Discrete maths text book, there was this question:
How many bit strings of length n are palindromes?
The answer is:
$2^\frac{n+1}{2}$ for odd and $2^\frac{n}{2}$ for even.
I searched it on the internet and people were saying that first $\frac{n}{2}$ ($\frac{n+1}{2}$ for odd ) can be selected arbitrarily and the next bits has to be determined.
I got the first part but I fail to understand the second. How can a palindrome can be determined by the first part?
Please explain it using an example. Thanks!
Best Answer
If a string is length $n$, then we can write it as either being length $2k+1$ if $n$ is odd, or $2*k$ if $n$ is even, where $k \in \mathbb Z$.
In either case, the first half of the digits determine the values of the second half of the digits. Indeed, let $$(a_m)_{m=1}^{n}$$ be a string that is a palindrome. Then $a_1 = a_n, a_2 = a_{n-1},\ldots$ If $n$ is odd, then $a_{k+1} = a_{k+1}$ otherwise $a_k = a_{k+1}$.
Thus, there are $2$ choices for the value of $a_1$, $2$ choices for $a_2$, $\ldots$, and $2$ choices for $a_k$. If $n$ is odd, then there are also two choices for the middle digits $a_{k+1}$. Combining, we see that if $n$ is odd, we have a total of $2^{k+1}$ possible choices; if $n$ is even then we have a total of $2^k$ possible choices. Substituting back for $n$ gives $2^{\frac{n+1}{2}}$ choices for $n$ odd and $2^{\frac{n}{2}}$ for $n$ even.