From Rock-Paper-Scissors to Stars and Bars
Date: 06/17/2014 at 21:58:18 From: KC Subject: combination problem Okay, I know the answer to this problem, but I don't know why the combination formula cannot be used to solve it. Please explain that to me. Three friends are playing a game in which each person simultaneously displays one of three hand signs: a clenched fist, an open palm, or two extended fingers. How many different combinations of the signs are possible? If I use 9 for the number of possible ways (3 friends * 3 signs) and 3 for the number of signs, and plug them into the combination formula ... well, you see 9!/3!(6!) doesn't work. The permutation formula doesn't work either. WHY NOT? Please, what am I missing here? Writing it all out does work. The answer is 10.
Date: 06/17/2014 at 22:51:16 From: Doctor Ian Subject: Re: combination problem Hi KC, Can you show me what you think the 10 ways are? - Doctor Ian, The Math Forum http://mathforum.org/dr.math/
Date: 06/18/2014 at 14:33:21 From: Doctor Ian Subject: Re: combination problem I asked for clarification, and this is what you sent me: Let's call clenched fist C; open palm O; and two fingers F. The possibilities are: CCC OOO FFF COO OCC FCC CFF OFF FOO COF That's 10 different combinations. WHY can't I use C(n,r) = n!/r!(n - r)!? If I try to organize your list by category, I get CCC, OOO, FFF All three the same FCC, OCC Two C's CFF, OFF Two F's COO, FOO Two O's COF All three different So this looks complete IF you're not distinguishing between who is doing what, i.e., FCC, CFC, and CCF are considered to be equivalent. But the fact that you're disregarding order means that a permutation formula isn't going to be appropriate, since permutations are about choosing different orders for a set of items. Also, note that when we talk about combinations, we're really talking about subsets, i.e., selections without replacement. The fact that you have items appearing more than once indicates that a combination formula isn't going to be appropriate, either. Since you are operating with replacement, you could start by noting that if order is significant, there are 3^3 = 27 different outcomes that you could have. So 17 of those are being "double counted" in some way, e.g., you want only one of each of these triplets: CCF, CFC, FCC CCO, COC, OCC FFC, FCF, CFF FFO, FOF, OFF OOC, OCO, COO OOF, OFO, FOO Honestly, I can't think of a straightforward way to use the permutation and combination formulas for this. But do you see why you shouldn't expect to be able to? - Doctor Ian, The Math Forum http://mathforum.org/dr.math/
Date: 06/18/2014 at 15:26:42 From: Doctor Peterson Subject: Re: combination problem Hi, KC. I was observing your interchange with Dr. Ian, and I have a method you might like. It's commonly called "stars and bars." You want to find the number of ways to fill three blanks with C, O, or F, allowing repetition, but ignoring order. So we can assume that every such combination is written in that order, C, O, F. This is equivalent to finding three numbers whose sum is 3, where each number can be 0, 1, 2, or 3. For example, the combination OFF is 0C + 1O + 2F 0 + 1 + 2 = 3. This in turn is equivalent to having 3 "stars," and placing four "bars" among them, so that the number of stars between two successive bars is the number to use in that position. For example, 0 + 1 + 2 is ... ||*|* *| ... because there are no stars between the first two bars, one between the next two, and two between the last two. Since the first and last bars are always in the same places, we can ignore them, and just place two bars among the stars: |*|* * Now, if we couldn't have zero, this would translate directly to choosing 2 of the 4 places where bars can be put. But unfortunately, we still don't have a combination problem, because we can put two or more bars in the same place, like so: *||* * So let's turn the problem inside-out yet again! We have three stars and two bars, AND want to find the number of ways to arrange ALL of them in order. That is, there are five spaces, and we want to put stars in three of them and bars in the other two. Now we see that the problem is equivalent to choosing two of five places to put bars, which (finally!) is a simple combination problem: C(5, 2) = 5!/(2!3!) = 10 There's your answer! And, just for fun, let's list the ten ways to arrange the stars and bars, and which answers they relate to, in terms of numbers or of rock-paper-scissors (that is, closed fist, open hand, two fingers): ||*** 0 + 0 + 3 FFF |*|** 0 + 1 + 2 OFF |**|* 0 + 2 + 1 OOF |***| 0 + 3 + 0 OOO *||** 1 + 0 + 2 CFF *|*|* 1 + 1 + 1 COF *|**| 1 + 2 + 0 COO **||* 2 + 0 + 1 CCF **|*| 2 + 1 + 0 CCO ***|| 3 + 0 + 0 CCC That was fun! I actually didn't know what form the answer would take when I started writing, but just knew that stars and bars would almost certainly work. - Doctor Peterson, The Math Forum http://mathforum.org/dr.math/
Date: 06/18/2014 at 15:57:27 From: KC Subject: Thank you (combination problem) Awesome explanation, Dr. Peterson! I have faith in my equations, but could NOT see the proper numbers. You rock.
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.