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

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 is equal to times the number of -element subsets of By the multiplication principle, there are such lists. Thus, the number of -element subsets of is equal to

This quantity is so important it gets its own name. It is known as a binomial coefficient, written

and read as “ choose .” On calculators, the option may be shown as “.”

TABLE 1.4. Common values of binomial coefficients.

Binomial coefficients

The binomial coefficient is often referred to as a way to count combinations, numbers of arrangements where order does not matter, as opposed to permutations, where order does matter. From the equation, one can see that the number of combinations of obtaining objects from is equal to the number of permutations of objects out of objects divided by the factorial of , the size of the subset desired (the number of permutations of the objects). This is accounting for the fact that in combinations, we do not care about the order of the objects in the subset.

By the one-to-one correspondence between -element subsets and binary lists with exactly ones, we have the following.