rel="nofollow" href="#fb3_img_img_35014d5c-4ad4-5a09-9810-edadeae6b182.png" alt="StartSet 1 comma ellipsis comma n EndSet"/> 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.
Subset
List
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 by permuting the elements of that subset. For instance, the three-element subset yields the lists: (1,3,4), (1,4,3), (3,1,4), (3,4,1), (4,1,3), and (4,3,1).
It follows that the number of lists of length made up of the elements
rel="nofollow" href="#fb3_img_img_35014d5c-4ad4-5a09-9810-edadeae6b182.png" alt="StartSet 1 comma ellipsis comma n EndSet"/> and binary lists of length 