Robert P. Dobrow - Probability

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.

There are -element subsets of .

There are binary lists of length with exactly ones.

There are ways to select a subset of objects from a set of objects when the order the objects are selected in does not matter.

Binomial coefficients are defined for nonnegative integers and , where . For or , set Common values of binomial coefficients are given in Table 1.4.