Читать книгу Probability - Robert P. Dobrow - Страница 30

In the last section, you learned how to count ordered lists and permutations. Here we count unordered sets and subsets. For example, given a set of distinct objects, how many subsets of size can we select when sampling without replacement? To proceed, we first show a simple yet powerful correspondence between subsets of a set and binary sequences, or lists. This correspondence will allow us to relate counting results for sets to those for lists, and vice versa.

A binary sequence is a list, each of whose elements can take one of two values, which we generically take to be zeros and ones. Our questions about subsets of size drawn from distinct objects is equivalent to asking: how many binary sequences of length contain exactly ones?

To illustrate, consider a group of people lined up in a row and numbered 1 to . Each person holds a card. On one side of the card is a 0; on the other side is a 1. Initially, all the cards are turned to 0. The cards from left to right form a binary list.

Select a subset of the people. Each person in the subset turns over his/her card, from 0 to 1. The cards taken from left to right form a new binary list. For instance, if and the first and third persons are selected, the corresponding list is .

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.

Subset	List