XERCISE 10.2.3: Using the bijection rule to count binary strings with even parit
ID: 3143800 • Letter: X
Question
XERCISE
10.2.3: Using the bijection rule to count binary strings with even parity.
Let B = {0, 1}. Bn is the set of binary strings with n bits. Define the set En to be the set of binary strings with n bits that have an even number of 1's. Note that zero is an even number, so a string with zero 1's (i.e., a string that is all 0's) has an even number of 1's.
(a)
Show a bijection between B9 and E10. Explain why your function is a bijection.
(b)
What is |E10|?
When answering the question use the bijection rule.
Explanation / Answer
(a) The bijection f is
f(x) = x + 0 if x E(9); x + 1 if x E(9)
Thus the function appends a 0 to a 9 bit string if it has even number of 1s and a 1 if it does not.
Proof that it is a bijection:
Let f(a) = f(b) = d
There are two cases:
(i) The last bit of d is 1
=> a + 1 = b + 1 = d
=> a = b
(ii) The last bit of d is 0
=> a + 0 = b + 0 = d
=> a = b
Since f(a) = f(b) => a = b, f is one-one.
Let s E(10), then there are two cases:
(i) The last bit is 1. Let r be the string with the last bit removed.
=> s = r + 1
But since s has even 1s, r must have odd 1s
=> s = f(r)
(ii) The last bit is 0. Let r be the string with the last bit removed.
=> s = r + 0
But since s has even 1s, r must have even 1s
=> s = f(r)
Thus every image in E10 has a pre-image in B9 and f is onto.
Therefore f is a bijection.
(b) Since there are 10 bits for every string in E10, total number of strings possible is 210.
The number of strings with even 1s = the number of strings with odd 1s = 210/2 = 29.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.