Count Me In : Count Me In Intro to Combinatorics
1. Snap, Crackle, and Pop are waiting in line to buy a bowl of cereal. In how many ways can they wait in line? For example, “Crackle – Snap – Pop” could be one such order. : 1. Snap, Crackle, and Pop are waiting in line to buy a bowl of cereal. In how many ways can they wait in line? For example, “Crackle – Snap – Pop” could be one such order. We have three choices for who is first in line to buy cereal: Snap, Crackle, or Pop: 1st Snap Crackle Pop If Snap goes first, there are two choices for who goes second: Crackle and Pop.
We can write out the options for who goes second: 2nd Crackle Pop Snap Pop Snap Crackle 1st Snap Crackle Pop
Slide 3 : Looking at the first case, if Snap goes first and Crackle goes second, only Pop is left,
so Pop must go third. In each case, there is only one person left to go third: 3rd Pop Crackle Pop Snap Crackle Snap 2nd Crackle Pop Snap Pop Snap Crackle 1st Snap Crackle Pop We can now count how many possibilities there are. Our answer is 6.
2. The starting lineup of the world’s greatest baseball team, the Philadelphia Phillies, has 9 members. In how many ways can manager Charlie Manuel arrange his starting lineup? : 2. The starting lineup of the world’s greatest baseball team, the Philadelphia Phillies, has 9 members. In how many ways can manager Charlie Manuel arrange his starting lineup? This is a similar question to the last one, except that it would take us a lot
longer to list all of the possible arrangements. We need a faster method. Let’s look back to the cereal question. There were 3 choices for the first person in line,
then 2 choices for the second person in line, then 1 choice for the last person in line.
Our answer was So, for our baseball problem, we have 9 choices for the first batter, times 8 choices for the second batter, times 7 choices for the third batter, and so on. Eventually, we will have just 1 choice for the ninth batter, since everyone else will have already been chosen to bat earlier. So, our answer will be This can be verified with a calculator. 362880
Factorials : Factorials This method of multiplying a number by the number 1 less than it, times the number two less than it, and so on until we multiply by 1 is so important in combinatorics (counting) that we give it its own name: factorial. The symbol for a factorial is an exclamation point. If you would like, the formal definition for factorial (!) is: You can plug in any number for n to find its factorial.
3. Find 5! : 3. Find 5! Using our definition from before,
5! = 5 x 4 x 3 x 2 x 1 = 120
4. Jackie, Tito, Jermaine, Marlon, and Michael are five friends who wish to create a singing group. They want one lead singer, one guitarist, and one drummer. Fortunately, all five are very gifted, so they can all play any role. If there are going to be 3 people in their singing group, in how many ways can they form a group so they can start rocking? : 4. Jackie, Tito, Jermaine, Marlon, and Michael are five friends who wish to create a singing group. They want one lead singer, one guitarist, and one drummer. Fortunately, all five are very gifted, so they can all play any role. If there are going to be 3 people in their singing group, in how many ways can they form a group so they can start rocking? We use a similar method from before. There are 5 choices for the lead singer, times 4 choices for the guitarist (since one person has already been selected), times 3 choices for the drummer (since two people have already been selected. Our answer is 5 x 4 x 3 = 60 In the future, we will want to be able to use this idea for lots of different problems. Let’s try to generalize it.
Permutations : Permutations Let’s say we have n things to choose from, and we are choosing j of them. Just like from before, we have n choices for the first one, n – 1 choices for the second one, and so on. Since we are only choosing j of the objects, not all of them, we will eventually finish with n – j + 1 choices for the last object. Let’s use the notation to symbolize choosing j out of n objects. As described above, Fortunately, there is an easier way to write this. We can multiply anything by 1 and not
change, so we will multiply by In mathematics, we call this the formula for the number of permutations. This is why we use a capital P to denote it.
5. Snow White has gone missing. The 7 dwarves are sending out a group of 3 of them to find her. One will carry a sac with food. One will carry binoculars to look for her. One will carry a gun for protection. How many possibilities are there for the arrangement of the search party? : 5. Snow White has gone missing. The 7 dwarves are sending out a group of 3 of them to find her. One will carry a sac with food. One will carry binoculars to look for her. One will carry a gun for protection. How many possibilities are there for the arrangement of the search party? This is a permutations problem because we are choosing 7 people for 3 different jobs, and we are asked to find the total number of arrangements. Isn’t this a bit faster than listing out 210 orderings? ? 210
6. Pythagoras, Euclid, Ptolemy, Archimedes, and Plato are brought together by a man named Raphael to meet at a school in Athens, Greece. There, Raphael wished to choose a group of 3 mathematicians to help prove a conjecture of his. How many groups of 3 mathematicians can he choose among the 5? : 6. Pythagoras, Euclid, Ptolemy, Archimedes, and Plato are brought together by a man named Raphael to meet at a school in Athens, Greece. There, Raphael wished to choose a group of 3 mathematicians to help prove a conjecture of his. How many groups of 3 mathematicians can he choose among the 5? We might be tempted to say that the answer is (you can check the math yourself), but this is not the case. Why not? In permutations, the order that you choose the objects matters. For example, in permutations, {A, B, C} and {A, C, B} would be counted separately. In our new problem, however, {Pythagoras, Euclid, Ptolemy} and {Pythagoras, Ptolemy, Euclid} are the same group, and should only be counted once. We need to make sure we don’t over count. We are dealing with groups of three mathematicians, so in permutations, each group would be counted 3! = 6 times. So, we divide the number of permutations by 6 to get our answer. 10
Combinations : Combinations To generalize, if we have n objects, and we are choosing j of them, and order does not matter, we have: This is known as the formula for combinations. It has many symbols, and and are the most commonly used.
7. A chicken in San Diego lays a dozen eggs, numbered 1 through 12. A member of the Padres farm team will choose 7 of these eggs to take to market. How many groups of 7 eggs can he choose? : 7. A chicken in San Diego lays a dozen eggs, numbered 1 through 12. A member of the Padres farm team will choose 7 of these eggs to take to market. How many groups of 7 eggs can he choose? The order of the eggs does not matter, so this is a combinations problem. 792
Thanks for joining us for Count Me In!Questions? Comments? Please e-mail Ben Zauzmer at bzauzmer@comcast.net. : Thanks for joining us for Count Me In!Questions? Comments? Please e-mail Ben Zauzmer at bzauzmer@comcast.net.