2.1 The Multiplication Principle and Permutations A fair coin is flipped two times. How many different outcomes are there for this experiment? How about flipping three times? (Use tree diagram)
Multiplication Principle: Suppose there is an operation that consists of making a sequence of two tasks n1 choices for the first task and, no matter how that first task was completed, there are always n2 possible choices for the second task. Then, there are n1 · n2 possible ways in which the sequence of two task can be completed. Example 1. Blue has 5 different shirts and 3 different pairs of pants. How many different outfits can Blue put together if an outfit consists of a shirt and a pair of pants? (5 × 3 = 15) General Multiplication Principle: Suppose there is an operation that consists of making a sequence of k tasks with n1 possible choices for the first task and, no matter what choice was made for the first task, there are always n2 possible choices for second task, and, no matter what choices were made for the first two tasks, there are always n3 possible choices for the third task, and so on. Then there are n1 · n2 · n3 · · · nk possible ways in which the sequence of k tasks can be make. Example 2. A state has issued license plates using a combination of six digits: 0 - 9. How many different license plates can be issued using this configuration? (10 × 10 × 10 × 10 × 10 × 10 = 106 ) Example 3. In recent years, a state has issued license plates using a combination of six digits: 0 - 9. How many different license plates can be issued using this configuration if no numbers can be repeated? (10 × 9 × 8 × 7 × 6 × 5 × 4) We may consider the above example like this: We select 6 numbers from 0 to 9 and arrangement them in different orders. Permutations: A permutation of a set of elements is an ordered arrangement of all the elements. Example 4. Find all the ways to arrange the elements in the set S = {a, b, c}. How about the set {a1 , a2 , · · · , an }? (Tree diagarm) Number of Permutations of n Objects: P (n, n) = n(n − 1)(n − 2)(n − 3) · · · 3 · 2 · 1 = n!. Here, we call ! as factorials. For convention, let 0! = 1.
1
Compute P (n, n) = n! using calculator: 1. input n; 2. press MATH; 3. scroll right to PRB; 4. select ! (Option 4); 5. press ENTER. Example 5. Find all the ways to arrange r elements in the set {a1 , a2 , · · · , an }. Number of Permutations of r Objects Taken from a Set of Size n: P (n, r) = n(n − 1)(n − 2) · · · (n − r + 2)(n − r + 1) =
n! . (n − r)!
Compute P (n, r) using calculator: 1. input n; 2. press MATH; 3. scroll right to PRB; 4. select nPr (Option 2); 5. input r; 6. press ENTER. Example 6. A baseball team has 13 players on the roster. How many nine-person batting orders can be formed from this team? P (12, 9) Up to this point, we have be concerned with arranging distinct objects. (That is, objects that can somehow be differentiated from each other.) What if some of the objects are identical (indistinguishable)? Example 7. How many distinguishable permutations of the word ADD are there? (count permutations sssuming two ’D’s are different. Then we cancel the order of ’D’s) Distinguishable Permutations (Section 2.3): Suppose a set of n elements consists of k distinct groups where group 1 has n1 identical elements, group 2 has n2 identical elements, ... , and group k has nk identical elements. So n = n1 + n2 + · · · + nk . Then there are n! n1 !n2 ! · · · nk ! distinguishable permutations of the set. Example 8. Find the number of distinct ways the letters in the “word” baaabe can be arranged. (6!/(2!3!1!)) Example 9. How many distinguishable ways can the letters in the word HULLABALOO be rearranged? 2
Example 10. Jilly and Milly go to the movies with 9 of their friends. They all sit in a row with exactly 11 seats. How many ways can these 11 friends be seated if Jilly and Milly must sit next to each other? (10!2!) Example 11. Billie Mae’s collection of plates fall into 3 categories. She has 3 “Frolicking Feline” plates, 4 “Star Wars” plates, and 5 “Nursery Story” plates. How many ways can Billie Mae arrange her plates on the shelf is plates from each category must be next to each other? (3!3!4!5!)
2.2 Combinations Example 12. How many different 5-card poker hands can be dealt from a standard deck of 52 cards? We may first consider the permutations P(52,5). Then we cancel out the order by dividing the number of permutations for only these five cards. That is 52! P (52, 5) = . 5! (52 − 5)!5!
Combinations: A combination of r distinct objects taken from a set of size n is a section of r of the objects (without concern for order). The number of combinations is: C(n, r) =
n! P (n, r) = . r! (n − r)!r!
Example 13. From a group of 12 people, how many ways can a committee of four be formed? C(12, 4) Compute C(n, r) using calculator: 1. input n; 2. press MATH; 3. scroll right to PRB; 4. select nCr (Option 3); 5. input r; 6. press ENTER. Example 14. A bag contains 5 green marbles, 3 blue marbles, and 7 purple marbles. a) In how many ways can a sample of 5 marbles be selected from the bag? C(15, 5) b) In how many ways can the sample of 5 marbles consist of exactly 3 purple marbles? C(7, 3)C(8, 2) 3
c) In how many ways can the sample of 5 marbles consist of at most 1 green marble? C(10, 5) + C(5, 1)C(10, 4) d) In how many ways can the sample of 5 marbles consist of at least 2 green marbles? C(15, 5) − (C(10, 5) + C(5, 1)C(10, 4)) e) In how many ways can the sample of 5 marbles contain only purple marbles? C(7, 5) f ) In how many ways can the sample of 5 marbles contain all of the blue marbles? C(12, 2) g) In how many ways can the sample of 5 marbles consist of exactly 2 green marbles or exactly 3 purple marbles? C(5, 2)C(10, 3) + C(7, 3)C(8, 2) − C(5, 2)C(7, 3) Example 15. A class of 30 students are electing a President, Vice-President, Secretary and Treasurer. They are also selecting a sub-committee of 4 students. In how many ways can this be done if a student cannot hold multiple positions? P (30, 4)C(16, 4) or C(30, 4)P (26, 4) Example 16. A class of 12 students will divide into 3 teams of 4. How many ways can this be done? C(12, 4)C(8, 4)C(4, 4) Example 17. Find out the number of solutions to the equation w + x + y + z = 10 if x, y, z are positive integers? C(9, 3) Example 18. Find out the number of solutions to the equation w + x + y + z = 10 if x, y, z are nonnegative integers? C(13, 3) Example 19. A school is putting together a committee. The committee will have a chair and an assistant chair chosen from a group of 10 teachers, 2 parents chosen from a group of 5 parents, and 2 students chosen from a group of 20 students. How many different committees are possible? P (10, 2)C(5, 2)C(20, 2)
4
