920 CHAPTER 13 Counting and Probability DEFINITION Combination A combination is an arrangement, without regard to order, of r objects selected from n distinct objects without repetition, where ≤ r n. The notation ( ) C n r , represents the number of combinations of n distinct objects taken r at a time. Listing Combinations List all the combinations of the 4 objects a b c d , , , taken 2 at a time.What is ( ) C 4, 2 ? Solution EXAMPLE 6 One combination of a b c d , , , taken 2 at a time is ab Exclude ba from the list because order is not important in a combination (this means that we do not distinguish ab from ba ).The list of all combinations of a b c d , , , taken 2 at a time is ab ac ad bc bd cd , , , , , so ( ) = C 4, 2 6 A formula for ( ) C n r , can be found by noting that the only difference between a permutation of r objects chosen from n distinct objects without repetition and a combination is that order is disregarded in combinations. To determine ( ) C n r , , eliminate from the formula for ( ) P n r , the number of permutations that are simply rearrangements of a given set of r objects. This can be determined from the formula for ( ) P n r , by calculating ( ) = P r r r , !. So, dividing ( ) P n r , by r! gives the desired formula for ( ) C n r , : ( ) ( ) ( ) ( ) = = − = − C n r P n r r n n r r n n r r , , ! ! ! ! ! ! ! ↑ Use formula (1). We have proved the following result: THEOREM Number of Combinations of n Distinct Objects Taken r at a Time The number of ways of selecting r objects from n distinct objects, ≤ r n, in which • repetition of objects is not allowed • order is not important is given by the formula ( ) ( ) = − C n r n n r r , ! ! ! (2) Based on formula (2), we discover that the symbol ( ) C n r , and the symbol ⎛ ⎝ ⎜⎜ ⎜ ⎞ ⎠ ⎟⎟ ⎟ n r for the binomial coefficients are, in fact, the same.The Pascal triangle (see Section 12.6) can be used to find the value of ( ) C n r , . However, because it is more practical and convenient, we will use formula (2) instead.
RkJQdWJsaXNoZXIy NjM5ODQ=