If n(S) = k, how many subsets will S have?
-
The number of subsets of S will be SUM i=0 to k of kCi where kCi represents "k choose i." Equivalently, we can use a combinatorial argument to get a nicer representation of this.
Think about it this way: every element in S is either in the subset or is not in the subset, so there are 2 possible choices for each element. Since there are k elements, there are 2^k possible choices for which elements to include.
Therefore, there are 2^k possible subsets of S.
Think about it this way: every element in S is either in the subset or is not in the subset, so there are 2 possible choices for each element. Since there are k elements, there are 2^k possible choices for which elements to include.
Therefore, there are 2^k possible subsets of S.