If x is a string, then xR is the reverse of the string. For example, if x = 1011, then xR = 1101. A string is a palindrome if the string is the same backwards and forwards (i.e., if x = xR). Let B = {0, 1}. The set Bn is the set of all n-bit strings. Let Pn be the set of all strings in Bn that are palindromes.

(c) Determine the cardinality of P7 by showing a bijection between P7 and Bn for some n.

The set Bn contains all binary strings of size n. The number of strings in the set is equal to 2n since there are n positions to fill and each position can be filled with either 0 or 1.

Therefore, total number of strings = 2 * 2 * … * 2 = 2n

The set Pn that contains all the n-bit strings that are palindrome is a subset of the set Bn.

(c)

The set P7 contains 7-bit binary strings that are a palindrome. Each bit can either be 0 or 1 and hence there are 2 ways to fill each position of the binary string. The number of strings in P7can be computed as follows:

The first bit should be equal to the seventh bit. Number of ways to fill the first bit = 2 ways

The second bit should be equal to the sixth bit. Number of ways to fill the second bit = 2 ways

The third bit should be equal to the fifth bit. Number of ways to fill the third bit = 2 ways

The fourth bit could either be 0 or 1. Number of ways to fill the fourth bit = 2 ways

Therefore, the cardinality of P7 is equal to the total number of ways to fill the first 4 bits of the 7-bit strings = 2*2*2*2 = 16

To create a bijection function between P7 and Bn, compute the value of n as shown below:

Number of strings in P7 = Number of strings in Bn

16 = 2n

24 = 2n

Therefore, the value of n = 4.

The string in the set B4 are as follows:

{0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111}

Proof for bijection:

1. The above function P7 to B4 is one-one or injective, that is, if f(x) = f(y), then x = y where x, y belongs to the set P7.

For all x and y belonging to set P7, there are no two strings x and y for which f(x) = f (y), where x is not equal to y.

Hence, the function is one-one or injective.

2. The above function is onto or surjective, that is, for all y belonging to B4, there exist f(x) such that f(x) = y.

In other words, there is no y that belongs to B4 which is not mapped to an element of the set P7. None of the element in the set B4 is left un-mapped.

Hence, the function is onto or surjective.

Since the function is injective and surjective, the function P7 to B4 is bijective.

Hence, proved.