Problem of the Month - April 2010: Subsets

In this problem we examine the number of subsets a given set might have. The set A is said to be a subset of the set B if all elements of A are elements of B. Another way to think of this is to think of one set as being "contained" by another, or "included" in the greater set. Similarly, a superset of a given set is one which "includes" all elements of its respective subset. For example, the set {1,2} is a subset of of the set {1,2,3}. By notation, a proper subset of a set B is one that is a subset of B but is not equal to B. Also, note that the null (empty) set, denoted { }, is a subset of all sets except itself.

• Determine the number of distinct subsets of the set {0,1,2} (remember the empty set!).
• Determine the number of distinct subsets of a set with n distinct elements.
• How many subsets of {{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}} satisfy the property that the union of each of the elements of the set forms the set {1,2,3,4}?

April 2010: Solution

To determine the number of distinct subsets of a set with n distinct elements, consider each of the n elements. This element can either be in a subset, or not in the subset; thus, there are two different classes of sets with respect to this one element. Furthermore, every such subset can be defined by whether each of the n elements is in or out of the set, so we know that there are a total of 2ⁿ distinct subsets. In the case of the subset {0,1,2}, for example, there are 2³=8 subsets.

From the paragraph above, we see that there are 64 subsets of the set, {{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}}. By counting the number of subsets whose union is not {1,2,3,4}, we can determine our desired value.

• If the union of the sets is "missing" one value, then the three sets that include that value must not be part of the subset; for example, the set, {{1,2},{1,3},{2,3}}, is missing each of the elements that contain the value "4." Furthermore, the subset could be missing at most one of the remaining 3 sets; for example, {{1,2},{1,3}}. Since there are four values to choose in the first step and three sets to choose in the second, there are 4*3=12 total subsets in this case.
• The set could also be "missing" two values, in which case it is fairly clear that there is a unique set that corresponds to the two chosen values; for example, if the set is "missing" values 2 and 4, the set in question must be {{1,3}}. There are 4C2=6 ways to choose the two missing elements.
• Finally, the set can be "missing" all four elements; that is, the set in question is the null set.

Adding together all of these cases, there are 12+6+1=19 ways that the union of the elements of the subset does not equal {1,2,3,4}; thus, there are 64-19=45 sets that do have the desired property.