Math 166, Fall 2011,cBenjamin Aurispa2.1 The Multiplication Principle and PermutationsSuppose a task T1can be performed in N1ways, a task T2can be performed in N2ways, . . . , and a taskTncan be performed in Nnways. Then, the number of ways of performing all the tasks T1, T2, . . . , Tninsuccession is N1N2· · · Nn.This means that the total number of ways to do a series of tasks is the PRODUCT of the number of waysto do each task.Examples1. At a restaurant, there are 5 appetizers on the menu, 10 main entrees, and 4 desserts. How many wayscan a meal be ordered if one appetizer, one main entree, and one dessert are chosen?2. Suppose I toss a coin 3 times and record the sequence of heads and tails and then roll a fair 6-sideddie 4 times and record the number rolled. How many different outcomes are possible?3. A test is given with 5 True/False questions and 20 multiple choice questions, each with 5 possibleanswers. If a True/False question can be left blank, but all MC questions must be answered, howmany ways are there to complete the test?4. How many 7-digit numerical codes are possible if(a) there are no restrictions?(b) the first digit cannot be 0?(c) no repetitions are allowed?(d) the first digit cannot be 0 and no repetitions are allowed?(e) the first digit cannot be 0, no repetitions are allowed, and the last digit must be odd?1Math 166, Fall 2011,cBenjamin Aurispa5. How many 4-letter “words” are possible in the English language (assuming we don’t care if the wordmakes sense) if(a) there are no restrictions?(b) repetitions are not allowed?(c) repetitions are not allowed and the word must start with and end with a vowel?I have 10 CDs and I want to put them in my CD case which has room for 10 CDs. In how many ways canI do this?Suppose I have a CD case which holds only 6 CDs. Then how many ways are there to put my 10 CDs inthe case?These two above are examples of permutations. A permutation of a set is an ordered arrangement of theobjects in the set. With permutations, ORDER MATTERS.In the first example, we found the number of ways to arrange all 10 of the 10 CDs by computing 10·9·8·. . .·2·1.This is called a factorial.Factorial: n! = n(n − 1)(n − 2) · · · · 3 · 2 · 1 [The factorial is found by pressing MATH and scrolling to PRB.]So, the answer to the first question can be written and computed as 10!.In general, the number of ways to arrange all n objects from a set of n distinct objects is n!.If we arrange only a subset of the n objects, as in the second example above, we get a smaller number. Thenumber of permutations of r objects taken from a set of n distinct objects is denoted P (n, r).P (n, r) =n!(n − r)!You don’t have to memorize this formula as we can calculate the number of permutations on the calculator.Go to MATH, then PRB, then 2:nPr. On the home screen, type: n nPr rFor the second example above, we could have also found the answer by computing P (10, 6).P (n, n), which represents the number of ways to arrange all n of n distinct objects is the same as .2Math 166, Fall 2011,cBenjamin AurispaExample: In how many ways can the letters in the word COPIER be arranged? In how many ways canthree of the letters be arranged?Example: In how many ways can gold, silver, and bronze medals be given in an Olympic track race if thereare 10 people running the race?Example: I have 3 different math books, 5 different history books, and 4 different science books that I wantto put on my bookshelf.In how many ways can all the books be arranged on the shelf?In how many ways can 10 of the books be arranged on the shelf?In how many ways can all of the books be arranged on the shelf if I want books of the same subjectmatter to be stacked together?Example: Carlos and Cami go to the movies with 6 of their friends.• In how many ways can all 8 of them be seated in a row?• In how many ways can they be seated if Carlos and Cami must sit in the middle two seats?• In how many ways can they be seated if Carlos and Cami must sit together and the other 6 friendsmust sit together.• In how many ways can they be seated if Carlos and Cami must sit together.3Math 166, Fall 2011,cBenjamin AurispaWith permutations, remember ORDER MATTERS. For example, the word COPIER is different from theword OPCERI. They are different permutations.Sometimes in a set of objects, there are objects which are not all distinct. For example, suppose I have 5identical red marbles, 6 identical green marbles, and 3 identical blue marbles and I want to know how manyDISTINGUISHABLE ways there are to arrange the marbles in a row. If I just said the answer was 14!,what’s the problem?Suppose you are given a set of n objects in which n1objects are alike of one kind, n2are alike of anotherkind, . . . , and nrare alike of another kind so that n1+ n2+ · · · +nr= n. Then, the number of permutationsof these n objects taken n at a time isn!n1!n2! · · · nr!Finish the marble problem.Example: How many ways are there to arrange the letters of the word CINCINNATI?2.2 CombinationsIf order does NOT matter, then we are finding a combination instead of a permutation.A combination is a selection of objects from a set, in which the ORDER DOES NOT MATTER.The number of combinations of n distinct objects taken r at a time is given byC(n, r) =n!r!(n − r)!You don’t have to memorize this. To do combinations on your calculator, go to MATH, then PRB,then 3:nCr. On the home screen type: n nCr rRemember, n is how many there are total of what you want and r is how many you actually want to choose.Example: How many ways are there to deal a 5-card hand out of a standard deck of 52 cards?4Math 166, Fall 2011,cBenjamin AurispaExample: There are 8 seniors and 6 juniors in the Math Club at a high school. In how many ways can amath team consisting of 4 seniors and 2 juniors be selected from the members of the Math Club?Example: A business has 5 employee vacancies to fill. In how many ways can the business fill these 5positions from a group of ten female and ten male applicants if the positions• May be filled by any combination of men and women.• Must be filled by 2 men and 3 women?When you are given a counting problem, the first question to ask yourself is DOES ORDER MATTER?This will tell you whether to use permutations or combinations. Sometimes, you may have to use both ofthese along with the multiplication principle.If you need to find the number of ways to do A OR B, you have to be careful about double