How to calculate the number of palindromes of a given number of characters?

It depends (slightly) on whether you want an odd number of digits in your string, or an even number of digits in your string.

Let's say that the "alphabet" contains $N$ different "characters". (These could be the digits 1-9, or the letters A-Z, or any other set of distinguishable symbols.) You want to know how many palindromes of a given length there are.

If the string length is to be even: Say the string length is $2k$. You can choose each of the first $k$ characters to be anything you want; once you've chosen those, the rest of the string is forced on you by the required symmetry. So there are $k$ free choices, each drawn from a set of $N$ characters; that means there are $N^k$ possibilities.

If the string length is to be odd: Say the string length is $2k+1$. You can choose each of the first $k+1$ characters to be anything you want; once you've chosen those, the rest of the string is forced on you by the required symmetry. So there are $k+1$ free choices, each drawn from a set of $N$ characters; that means there are $N^{k+1}$ possibilities.

So, for example, if your alphabet consists of the 26 lowercase letters a-z, and you want a string with 9 characters, then $N=26$ and the string has length $2k+1$ with $k=4$; therefore the number of possible palindromes is $26^5=11,881,376$.

Assuming an alphabet of size N, and a string length of k:

$N^{⌈k/2⌉}$

N to the power of the ceiling of half the string length.

(Ceiling means always round up for any decimal)

This is because:

$k = 1$ will have $N$ possibilities and the string will be in the format: $N_1$

$k = 2$ will have $N$ possibilities and the string will be in the format: $N_1N_1$

$k = 3$ will have $N^2$ possibilities and the string will be in the format: $N_1N_2N_1$

$k = 4$ will have $N^2$ possibilities and the string will be in the format: $N_1N_2N_2N_1$

$k = 5$ will have $N^3$ possibilities and the string will be in the format: $N_1N_2N_3N_2N_1$

etc...

Even though every even length string has an added a character compared to the odd string of one less in length, because it is a palindrome, this added character will be a duplicate. It's position and character is decided by its mirror.