Probability - Robert P. Dobrow

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

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 k made up of the elements StartSet 1 comma ellipsis comma n EndSet is equal to k factorial times the number of k-element subsets of StartSet 1 comma ellipsis comma n EndSet period 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 k-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 “n choose k.” On calculators, the option may be shown as “n upper C r.”

Binomial coefficients
StartBinomialOrMatrix n Choose 0 EndBinomialOrMatrix equals StartBinomialOrMatrix n Choose n EndBinomialOrMatrix equals 1
StartBinomialOrMatrix n Choose 1 EndBinomialOrMatrix equals StartBinomialOrMatrix n Choose n minus 1 EndBinomialOrMatrix equals n
StartBinomialOrMatrix n Choose 2 EndBinomialOrMatrix equals StartBinomialOrMatrix n Choose n minus 2 EndBinomialOrMatrix equals n left-parenthesis n minus 1 right-parenthesis slash 2
StartBinomialOrMatrix n Choose k EndBinomialOrMatrix equals StartBinomialOrMatrix n Choose n minus k EndBinomialOrMatrix

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

      COUNTING k-ELEMENT SUBSETS AND LISTS WITH k ONES

      There are StartBinomialOrMatrix n Choose k EndBinomialOrMatrix k-element subsets of StartSet 1 comma ellipsis comma n EndSet.

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

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

       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

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