0 comma 0 comma 0 right-parenthesis"/>.
Conversely, given a list of zeros and ones, we select those people corresponding to the ones in the list. That is, if a one is in the th position in the list, then person is selected. If the list is , then all but the second person are selected.
This establishes a one-to-one correspondence between subsets of and binary lists of length . Table 1.3 shows the correspondence for the case .
A one-to-one correspondence between two finite sets means that both sets have the same number of elements. Our one-to-one correspondence shows that the number of subsets of an -element set is equal to the number of binary lists of length . The number of binary lists of length is easily counted by the multiplication principle. As there are two choices for each element of the list, there are binary lists. The number of subsets of an -element set immediately follows as .
TABLE 1.3. Correspondence between subsets and binary lists.
1.7.1 Combinations and Binomial Coefficients
Our goal is to count the number of binary lists of length with exactly ones. We will do so by first counting the number of -element subsets of an -element set. In the subset-list correspondence, observe that every -element subset of corresponds to a binary list with ones. And conversely, every binary list with exactly ones corresponds to a -element subset. This is true for each . For instance, in the case and , the subsets are
with corresponding lists
Given a specific -element subset, there are ordered lists that can be formed
