A palindrome over Σ is a string x ∈ Σ n that reads the same backward and forward—like 0110, TESTSET, or (ignoring spaces and punctuation) SIT ON A POTATO PAN, OTIS!. 1 How many 6-letter palindromes...

A palindrome over Σ is a string x ∈ Σ

n

that reads the same backward and forward—like 0110,

TESTSET, or (ignoring spaces and punctuation) SIT ON A POTATO PAN, OTIS!.

1 How many 6-letter palindromes (elements of {A, B, . . . , Z}

6) are there?

2 How many 7-letter palindromes (elements of {A, B, . . . , Z}

7) are there?

3 Let n ≥ 1 be an integer, and let Pn denote the set of palindromes over Σ of length n. Define a bijection f : Pn → Σ^k

(for some k ≥ 0 that you choose). Prove that f is a bijection, and use this bijection to write a formula for |Pn| for arbitrary n ∈ Z≥