The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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.
Associated Topics:
High School Permutations and Combinations

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/