# How do I show that there are more palindromes of length 14 than palindromes of length 12?

Let $P_{12}$ and $P_{14}$ be the sets of palindromes of length 12 and 14, respectively, over some alphabet, say, $\{a,b,c\}$.

I can show that $|P_{12}|\leq|P_{14}|$ easily by using the injective map $w\mapsto awa$.

I am trying to show that $|P_{14}|>|P_{12}|$ by showing that there is no injective map from $P_{14}$ to $P_{12}$. It seems like an obvious fact, but I don't immediately see how to prove this.

How can I prove that there is no injective map from $P_{14}$ to $P_{12}$?

• Why not compute the numbers simply? $\mid P_{12}\mid=3^6$ and $\mid P_{14}\mid =3^7$. – DKal Jun 9 '14 at 16:38
• Note that you have to ensure the alphabet has more than one letter. If the alphabet is $\{a\}$ then there is just one word of each length, and its a palindrome. – Asaf Karagila Jun 9 '14 at 16:40

Since the sets are finite it's enough to point out that your map from $P_{12}$ to $P_{14}$ is injective but not surjective.
You can show that any palindrome in $P_{14}$ of $bsb$ type where $s \in P_{12}$ is not hit by your injective map.
let $f:P_{14} \rightarrow P_{12}$ be a map such that $f(bsb)=f(s)$ now this function is clearly surjective. However $f(asa)=f(bsb)$ and so the map is not an injective one.