Report

Permutations and Combinations Section 3 Objectives: • Use factorial notation to represent the number of permutations of a set of objects. • Calculate the number of permutations of n objects taken r at a time. • Calculate the number of combinations of n objects taken r at a time. • Apply the theory of permutations and combinations to solve counting problems. Permutations • Notation: P(n , r) = nP r • For permutations, order is important! So abc and acb are different permutations. Permutations cont. (2) How many permutations are there of the letters a, b, c, and d? Write the answer using P(n, r) notation. We write the letters a, b, c, and d in a line without repetition, so abcd and bcad are two such permutations. The slot diagram indicates there are 4 × 3 × 2 × 1 = 24 possibilities. This can be written as = 4P4 Permutations cont. (3) How many permutations are there of the letters a, b, c, d, e, f, and g if we take the letters three at a time? Write the answer using P(n, r) notation. The slot diagram indicates there are 7 × 6 × 5 = 210 possibilities. This can be written in permutation notation as Factorial Notation So And P(4, 4) = 4 P4 = 4! • Compute (8 – 3)!. = 120 • Compute . Factorial Notation cont. (2) So P(n, r) is the product of r factors beginning with n and each then decreasing by 1 . • Example: A 12-person theater group wishes to select one person to direct a play, a second to supervise the music, and a third to handle publicity, tickets, and other administrative details. In how many ways can the group fill these positions? • Solution: Order does matter so this is a permutation of selecting 3 people from 12. Using a slot diagram, we see 3 factors beginning with 12: (12)(11)(10) = 1,320 ___ ___ ___ Combinations • How many three-element subsets can be chosen from a set of five objects? • Order is not important, so this is a combination problem. • How many four-person committees can be formed from a set of 10 people? • Solution: Order is not important, so this is a combination problem. C(10, 4) = P(10, 4) / 4! Combinations cont. (2) • • A syndicate has $15 million to spend on tickets for a lottery. Tickets cost $1 and contain a combination of six numbers from 1 to 44. Does the syndicate have enough money to buy enough tickets to be guaranteed a winner? Solution: The combination of 6 numbers from the 44 possible gives the number of different tickets. That is, C(44, 6) = 7,059,052. Thus, the syndicate has more than enough money to buy enough tickets to be guaranteed a winner. • In the game of poker, five cards are drawn from a standard 52-card deck. How many different poker hands are possible? • In the game of bridge, a hand consists of 13 cards drawn from a standard 52card deck. How many different bridge hands are there? Combining Counting Methods Two men and two women from a firm will attend a conference. If the firm has ten men and nine women, in how many different ways can the conference attendees be selected? Solution: The answer is not C(19, 4) since this includes options like four men and no woman being sent to the conference. Stage 1: Select the two women from the nine available. Stage 2: Select the two men from the ten available. Thus, choosing the women and then choosing the men can be done in ways. Combining Counting Methods cont. (2) A 16-member consortium wishes to choose a committee consisting of a president, a vice president, and a three-member executive board. In how many different ways can this committee be formed? Solution: We will count this in two stages: (a) choosing the president and vice president from the consortium, (b) choosing an executive board from the remaining members. Stage 1: Choose the president and vice president. This can be done in P(16, 2) ways. Stage 2: Select the executive board. This can be done in C(14, 3) ways. Total: Pascal’s Triangle For example, consider the set {1, 2, 3, 4} and the 4th row of Pascal’s triangle: 1 4 6 4 1. Pascal’s Triangle cont. (2) For example, again consider the 4th row of Pascal’s triangle: 1 4 6 4 1 . C(4, 0) = 1 C(4, 1) = 4 C(4, 2) = 6 C(4, 3) = 4 C(4, 4) = 1 Pascal’s Triangle cont. (3) Assume that a pharmaceutical company has developed five antibiotics and four immune system stimulators. In how many ways can we choose a treatment program consisting of three antibiotics and two immune system stimulators to treat a disease? Use Pascal’s triangle to speed your computations. Solution: We will count this in two stages: (a) choosing the antibiotics, (b) choosing the immune system simulators. Stage 1: Choosing 3 antibiotics from 5 can be done in C(5, 3) ways. Stage 2: Choosing 2 immune system simulators from 4 can be done in C(4, 2) ways. Total: C(5, 3) × C(4, 2) = 10 × 6 = 60 ways.