Probability. Robert P. Dobrow. Читать онлайн. Hotlib. HOTLIB.NET

the elements of that subset. For instance, the three-element subset StartSet 1 comma 3 comma 4 EndSet yields the 3 factorial equals 6 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 StartSet 1 comma ellipsis comma n EndSet is equal to k factorial times the number of -element subsets of By the multiplication principle, there are n times left-parenthesis n minus 1 right-parenthesis times midline-horizontal-ellipsis times left-parenthesis n minus k plus 1 right-parenthesis such lists. Thus, the number of -element subsets of StartSet 1 comma ellipsis comma n EndSet is equal to

StartFraction n times left-parenthesis n minus 1 right-parenthesis times midline-horizontal-ellipsis times left-parenthesis n minus k plus 1 right-parenthesis Over k factorial EndFraction equals StartFraction n factorial Over k factorial left-parenthesis n minus k right-parenthesis factorial EndFraction period

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

StartBinomialOrMatrix n Choose k EndBinomialOrMatrix equals StartFraction n factorial Over k factorial left-parenthesis n minus k right-parenthesis factorial EndFraction comma

and read as “ choose .” On calculators, the option may be shown as “ n upper C r .”

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 StartBinomialOrMatrix n Choose k EndBinomialOrMatrix -element subsets of StartSet 1 comma ellipsis comma n EndSet .

There are StartBinomialOrMatrix n Choose k EndBinomialOrMatrix binary lists of length with exactly ones.

There are StartBinomialOrMatrix n Choose k EndBinomialOrMatrix 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 0 less-than-or-equal-to k less-than-or-equal-to n . For k less-than 0 or k greater-than n , set StartBinomialOrMatrix n Choose k EndBinomialOrMatrix equals 0 period 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

Скачать книгу