Let be a set with six elements. In how many different ways can one select two not necessarily distinct subsets of so that the union of the two subsets is ? The order of selection does not matter; for example, the pair of subsets represents the same selection as the pair
Solution
Call the two subsets and For each of the elements in we can assign it to either or both. This gives us possible methods of selection. However, because the order of the subsets does not matter, each possible selection is double counted, except the case where both and contain all elements of So our final answer is then
Note: because we can order selections and in two ways, but since order does not matter in the problem, we should only count them once, ie we need to divide by two. We first need to subtract one for the count because there is one case in which and are identical and so while the rest of the “different” cases are counted twice, this one was only counted once so we should subtract one from the total count, divide by two, and add back that distinct one case. Or we could just add one, making all of the problem’s different cases counted twice, and divide it all by two, which is