Question

If w is a string of english letters a–z (all uppercase for the purposes of this problem), let wr denote the reverse of w; (train)r=niart. a palindrome is a string that is its own reversal: w = wr. for example, bzrzb is a palindrome of length 5. we are not concerned with whether it is an actual english word. find a formula for the number of palindromes of length k. you will need to treat odd (k = 2m + 1) and even (k = 2m) lengths differently

Answer 1

`f(x)=\left \{\begin{array}{rl}26^{(k)/(2)}&\text{for k even}\\26^{(k+1)/(2)}&\text{for k odd}\end{array}\right.`

Explanation:

Half the length of the palindrome can be any possible sequence of the 26 available letters. The other half is constrained to be the reverse of the same sequence. For odd length sequences, the middle letter can be any of the 26.

So, for k even, the number of palindromes is 26^(k/2). For k odd, the number is 26·26^((k-1)/2) = 26^)((k+1)/2).