0
$\begingroup$

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}$?

$\endgroup$
  • $\begingroup$ Why not compute the numbers simply? $\mid P_{12}\mid=3^6 $ and $\mid P_{14}\mid =3^7 $. $\endgroup$ – DKal Jun 9 '14 at 16:38
  • 1
    $\begingroup$ 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. $\endgroup$ – Asaf Karagila Jun 9 '14 at 16:40
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

You can show that any palindrome in $P_{14}$ of $bsb$ type where $s \in P_{12}$ is not hit by your injective map.

$\endgroup$
1
$\begingroup$

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.

$\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.