Probability. Robert P. Dobrow

Чтение книги онлайн.

СКАЧАТЬ 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 СКАЧАТЬ