6
$\begingroup$

How can one count the number of all $n$-digit palindromes? Is there any recurrence for that?

I'm not sure if my reasoning is right, but I thought that:

For $n=1$, we have $10$ such numbers (including $0$).
For $n=2$, we obviously have $9$ possibilities.
For $n=3$, we can choose 'extreme digits' in $9$ ways. Then there are $10$ possibilities for digits in the middle.
For n=4, again we choose extreme digits in $9$ ways and middle digits in $10$ ways
and, so on.

It seems that for even lengths of numbers we have $9 \cdot 10^{\frac{n}{2}-1}$ palindromes and for odd lengths $9 \cdot 10^{n-2}$. But this is certainly not even close to a proper solution of this problem.

How do I proceed?

$\endgroup$
  • $\begingroup$ Hint: How many $7$-digit or $8$-digit palindromes start with $1000$? How many start with $1001$? $\endgroup$ – Erick Wong Jan 26 '13 at 20:52
8
$\begingroup$

Details depend on whether for example $0110$ counts as a $4$-digit palindrome. We will suppose it doesn't. This makes things a little harder.

If $n$ is even, say $n=2m$, the first digit can be any of $9$, then the next $m-1$ can be any of $10$, and then the rest are determined. So there are $9\cdot 10^{m-1}$ palindromes with $2m$ digits.

If $n$ is odd, say $n=2m+1$, then the same sort of reasoning yields the answer $9\cdot 10^{m}$.

$\endgroup$
  • $\begingroup$ Thanks. I see I was wrong about odd ns. $\endgroup$ – Hagrid Jan 26 '13 at 21:05
  • $\begingroup$ @Hagrid: In the odd case, the "middle" person can be anything. $\endgroup$ – André Nicolas Jan 26 '13 at 22:07
4
$\begingroup$

An n-digit number abc...xyz can be mapped to the 2n-digit palindrome abc...xyzzyx...bca, and to the (2n-1)-digit palindrome abc...xyzyx...bca. So the number of 2n-digit palindromes and (2n-1)-digit palindromes is simply the number of n-digit numbers: $9 \times 10^{n-1}$.

$\endgroup$

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.