Section 4.8: Combinations In the last section we solved problems in which the order that the objects are arranged was important. We used the Counting Principle and a Permutation formula to answer the questions that were asked. The permutation formula and the Counting Principle over count when the order that the objects we select are placed is not important. Order is not always important. For instance if I purchase an Arizona Pick Lottery ticket I only need to match the numbers drawn to win and the order the numbers were drawn does not affect whether I win or not. If I match all 6 numbers, regardless of order I win. Example: Holly, Sarah, Jen and Marsha are at a Zac Brown concert. A stage hand comes up to the group and tells them that 3 of them can go backstage to meet the band. How many different groupings are possible? If you used the Counting principle you would make three slots, fill the slots with numbers and multiply to get 24 different groups. ____ * ____ * ____ 1st 2nd 3rd 4*3*2 = 24 If you tried to list all of the groups possible, you would run out of groups long before you get to 24. In fact there are only 4 groups possible. Basically each group picks 3 girls and leaves 1 girl out. It’s easy to make the list if you just leave a different girl out each time you make an entry to the list. Here are the 4 possible groups: Holly, Sarah, Jen Holly, Sarah, Marsha Holly, Jen, Marsha Sarah, Jen, Marsha Any other group you might list would just be one of these groups with the names rearranged. The counting principle over counts when only the objects selected is important and the order that they are selected in is not important. When the order of selection is not important the problem is a COMBINATION problem. Here is a definition of the topic we cover in this section – Combination. Combination is a way of selecting members from a grouping, such that the order of selection does not matter. When order is not important we can’t just make lines for each choice and put numbers over the lines and multiply. This will over count when order is not important. We will need a formula to find out how many combinations (arrangements in which order is not important) from a group are possible. The formula we need: n Cr  n!  n  r  !r ! n = total number of objects r = number being selected The Zac Brown problem could be solved using this formula. In this case the n = 4, as the group has 4 people and the r = 3 as only 3 of them can go backstage. 4C3 4! 4∗3∗2∗1 4∗3∗2∗1 = (4−3)!3! = (1)!∗3∗2∗1 = 1∗3∗2∗1 = 4 (thus there are 4 possible groups) Example: How many different ways can three people from Dave, Dan, Julie, Amanda and Steve be selected to attend a meeting? Before putting pencil to paper, I need to ask myself if the order the people are selected is important or not. If I think the order is important then it is a permutation problem and I can use the permutation formula, or make lines and multiply. If I think order is not important then I need to use the combination formula. That is if you think picking Dan, Dave and Julie to attend meeting is different the picking Dave, Julie and Dan to attend the meeting you would solve this problem using the techniques from section 4.7. I don’t think this would be correct. The order you list the people selected to attend a meeting is likely not important. This is supposed to be a combination problem. I will solve it using the combination formula. 5 C3  5!   5  3!3! Answer: 10 Example: 10 GCC students have applied for a scholarship. 6 students will be chosen to receive this scholarship, how many different ways can these 6 be chosen? Because the order that you were selected doesn’t matter, and only the fact that you are selected matters this is a combination problem. 10 C6  Answer: 210 10! (10−6)!6! Homework #1-17 1) An ice cream parlor has 20 different flavors. Cynthia orders a banana split and has to select 3 different flavors. How many different selections are possible? 2) A textbook search committee is considering 8 books for possible adoption. The committee has decided to select three of the eight for further consideration. In how many ways can they do so? 3) The drama club is planning a trip to New York. While in New York they want to attend 3 plays out of 10 plays they would like to see. How many different groups of 3 plays can they select to attend? 4) Neo wants to download 6 different songs. He only has enough money to purchase 4. In how many ways can he select 4 or 6 songs to purchase? 5) In how many ways can you select a committee of 4 students out of 12 students? 6) In how many ways can you select 3 different vegetables from 8 vegetables? 7) 3 different varieties of flowers are going to be placed in a vase. There are 5 different flowers to choose from. How many combinations can be made from the 5 varieties of flowers? 8) How many 3 topping pizzas could be made if you have 10 toppings to choose from (assume each topping can only be used once)? 9) The US senate consists of 100 senators, two from each state. A committee consisting of five senators is to be formed. How many are possible? 10) There are 6 restaurants you would like to try on your next vacation. You only have time to try 4 of them when you go on vacation. How many groups of restaurants can you choose? 11) You need to upload a few videos to watch on a plane. You only have storage capacity to add 5 new videos, but have 12 videos to choose from. How many combinations videos can you choose? 12) How many groups of 2 sevens can be made from the 4 sevens in a deck of cards? 13) How many groups of 3 kings can be made from the 4 kings in a deck of cards? 14) How many groups of 4 hearts can be made from the 13 hearts in a deck of cards? 15) How many groups of 3 spades can be made from the 13 spades in a deck of cards? 16) How many groups of 2 black cards can be made from the 26 black cards in a deck of cards? 17) How many groups of 5 red cards can be made from the 26 red cards in a deck of cards? There are times when it is okay and necessary to use both the Counting Principle and the Combination formula to solve a problem. The following example is a blended problem that uses the combination formula along with the counting principle. Example: At a Chinese restaurant, dinner for 8 people consists of 3 items from column A, 4 items from column B and 3 items from column C. If columns A, B and C have 5, 7 and 6 items respectively how many different dinner combinations are possible? This is where things get very confusing; I am using the counting principle for this problem, along with the combination formula. Knowing how to combine rules can be tricky. I will use combinations for the number of choices of each item, and the counting principle for the total number of combinations. Choose 3 of 5 items from column A 5C3 = 10 Choose 4 of 7 items from column B 7C4 = 35 Choose 3 of 6 items from column C 6C3 = 20 Now multiply the results: 10*35*20 = 7000 Answer there are 7000 different combinations possible. Example: How many groups of 3 hearts and 5 spades can be made from the 13 hearts and 13 spades in a deck of cards? Choose 3 of 13 hearts 13C3 = 286 Now multiply the results: 286*1287 = 368,082 Answer: There are 368,082 ways Choose 5 of 13 spades 13C5 = 1287 Homework #18 – 32 18) On an English test, Tito must write an essay for 3 of 5 questions in part one and 4 of 6 questions in part two. How many different combinations of questions can he answer? 19) A couple is planning a party. They need to pick 2 of 6 dinners to offer, and 3 of 5 desserts. How many different combinations can they pick? 20) An 8 person committee is being formed from a club that has 10 seniors and 8 juniors. How many committees can be formed if the committee must have 6 seniors and 2 juniors? 21) 6 members of a club will be selected to attend a conference. The club has 8 female and 7 male members. How many different groups can be selected if 3 male and 3 females must be selected? 22) A club plans to visit 3 of 5 landmarks in California and 2 of 4 landmarks in Oregon. How many different groups of sites can they select? 23) At a medical research center an experimental drug is to be given to 12 people, 6 men and 6 women. If 10 men and 9 women have volunteered to be given the drug, in how many ways can the researcher choose the 12 people to be given the drug? 24) At a medical research center an experimental drug is to be given to 20 people, 12 children and 8 adults. If 15 children and 9 adults have volunteered to be given the drug, in how many ways can the researcher choose the 20 people to be given the drug? 25) Michael is sent to the store to get 5 different bottles of regular soda and 3 different bottles of diet soda. If there are 10 different types of regular soda, and 7 different types of diet soda to choose from, how many different choices does Michael have? 26) A couple is throwing a party. They need to pick 5 different kinds of beer from the 12 beers being offered, and they need to pick 4 snacks from the 9 snacks being offered. How many different choices do they have? 27) How many groups of 2 sevens and 3 threes can be made from the 4 sevens and 4 threes in a deck of cards? 28) How many groups of 3 kings and 1 jack can be made from the 4 kings and 4 jacks in a deck of cards? 29) How many groups of 4 hearts and 2 spades can be made from the 13 hearts and 13 spades in a deck of cards? 30) How many groups of 3 spades and 2 clubs can be made from the 13 spades and 13 clubs in a deck of cards? 31) How many groups of 2 black cards and 4 red cards can be made from the 26 black cards and 26 red cards in a deck of cards? 32) How many groups of 5 red cards and 1 black card can be made from the 26 red cards and 26 black cards in a deck of cards? Answers: 1) 20C3 = 1140 3) 10C3 = 120 5) 12C4 = 495 7) 5C3= 10 9) 100C5 = 75,287,520 11) 12C5 =792 13) 4C3 = 4 15) 13C3 =286 17) 26C5 =65,780 19) 6C2 * 5C3 = 15*10 = 150 21) 7C3 * 8C3 = 35*56 = 1960 23) 10C6 * 9C6 = 210*84 = 17,640 25) 10C5 * 7C3 = 252*35 = 8,820 27) 4C3 * 4C2 = 4*6 = 24 29) 13C4 * 13C2 = 715 * 78 = 55,770 31) 26C2 * 26C4 = 325*14950 = 4,858,750