Problem . Describe a bijection between the binary representations of the integer

Question

Problem . Describe a bijection between the binary representations of the integers be- tween o and 2"- 1 and the subsets of an n-element set. What does this tell you about the number of subsets of an n-element set? You may have seen a notation like (1), c(n,k), or C which stands for the number of ways to choose a k-element subset from an n-element set. The number ()s read as "n choose k" and is called a binomial coefficient for reasons we will see later on Another frequently used way to read the binomial coefficient notation is “the number of combinations of n things taken k at a time." [1,2,3, , n]. For example, the set We will work with subsets of the n-element set n of two-element subsets of [4] is (fi, 2, 1,3, 1,4 (2, 3, 2, 4, (3, 41 This example tells us that 2

Explanation / Answer

A function is called a bijection if it is both one-one and onto function. In otherwords, a bijection is function which maps each element of a set 'A' to one and onlly one element of the set 'B', and each element is 'B' has a corresponding element in set 'A'.

A binary representation is something such as (a,b)

When we are considering the integers between 0 and 2n-1 and the subsets of an n-element set:

Suppose we take n=3,

Then we are considering integers from 0 to 23-1=7 i.e the integers 0,1,2,3,4,5,6,7. So, we have the set, A={0,1,2,3,4,5,6,7}

Also, let us consider a set with n=3 elements, let this set be B={x,y,z}.

The possible subsets of B are:

{},{x}, {y}, {z}, {x,y}, {x,z}, {y,z}, {x,y,z}.

So the set of subsets is: [{},{x}, {y}, {z}, {x,y}, {x,z}, {y,z}, {x,y,z}.]

In the above we see that there are 8 integers in set A and there are 8 possible subsets of the set of subsets of set B.

So, we can define a bijection by relating one element in set A to one unique subset of the set B.

One such example could be [(0,{}), (1,{x}), (2,{y}), (3,{z}), (4,{x,y}), (5,{x,z}), (6,{y,z}), (7,{x,y,z}) ]

Thus, we can say that the number of possiple unique subsets of a set with n-elements is 2n-1.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.