Probability. Robert P. Dobrow

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.

      COUNTING k-ELEMENT SUBSETS AND LISTS WITH k ONES

      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.

       Example 1.20 A classroom of ten students has six females and four males. (i) What are the number of ways to pick five students for a project? (ii) How many ways can we pick a group of two females and three males?

      1 There are ways to pick five students.

      2 There are ways to pick the females, and ways to pick the males. By the multiplication principle, there