Choose Three People from Five

Date: 05/09/2001 at 19:53:02
From: Barbara Moyers
Subject: Combinations

How would you work out this problem?

Find the number of combinations 

                              choose 3 people from 5

Must be done like this    _ times_times_
                          _______________
                          5 times 4 times 3

Date: 05/10/2001 at 13:00:16
From: Doctor Greenie
Subject: Re: Combinations

Hi, Barbara -

You won't have any luck trying to write the answer in the form you 
have shown. In the fraction you have shown, the "5 times 4 times 3" 
needs to be in the numerator.

Let's look into this and see where the formula comes from for 
determining the number of ways of choosing 3 people from a group of 5.

If we have a group of "m" objects and we are choosing "n" of them, 
mathematicians call the number of ways of doing that "m choose n".  
It is often written in symbols as "mCn" or "C(m,n)".  I will use the 
"C(m,n)" notation in the discussion below.

Most often, the value of the expression C(m,n) is taught as being

                m!
  C(m,n) = -----------
            (n!)(m-n)!

So in your example you would have

               5!         5*4*3*2*1     5*4*3      120      120
  C(5,3) = ---------- = ------------ = ------- = ------- = ----- = 10
           (3!)(5-3)!   (3*2*1)(2*1)    3*2*1     6 * 2      12

The middle expression, with "5*4*3" in the numerator and "3*2*1" in 
the denominator, is the form of the answer you are supposed to use.

But instead of just memorizing a magical formula, let's look at what 
the formula means. You will better understand this whole idea of "5 
choose 3" (and the more general idea of "m choose n") if you can 
understand why the value of "5 choose 3" is a fraction with "5*4*3" in 
the numerator and "3*2*1" in the denominator.

Let's suppose first that there is an election with five candidates, 
and the three candidates with the highest vote totals get the offices 
of president, vice president, and assistant vice president, 
respectively. How many different outcomes are there in this election?

Well, any one of the five candidates might come in first; for any of 
those five possibilities, any one of the remaining four candidates 
might come in second, giving 5*4 = 20 possible outcomes for the first 
two offices; and for any of those 5*4 = 20 possible outcomes, any of 
the remaining three candidates might come in third, giving a grand 
total of 5*4*3 = 60 possible outcomes to the election.

So the "5*4*3" in the numerator of "5 choose 3" is the number of ways 
of choosing three objects from a group of five if the order of 
selection is important.

Now let's look at the same election with five candidates, but instead 
of the top three vote getters getting the titles of president, vice 
president, and assistant vice president, they just become a committee 
of three, with nothing to distinguish the three positions. The order 
of selection is not important; this is the situation where the concept 
of "5 choose 3" applies. How many outcomes are there in this case?

Think of the list of all of the 5*4*3 = 60 possible outcomes of the 
election if order is important; and think of a particular combination 
of three top vote getters - let's call them A, B, and C. How many of 
the entries in the list of the 60 possible outcomes of the election 
have the same combination of candidates A, B, and C but in different 
orders? Well, any one of the three could have been the top vote 
getter; and for each of those three possibilities, either of the other 
two could have been the next highest vote getter, giving 3*2 = 6 
possible orders for the first two of the three; and for each of those 
six possible orders, there would be only one possibility for the 
third-place vote getter. So the number of different ways the 
particular combination of candidates A, B, and C could have been 
obtained is 3*2*1 = 6.

So the "3*2*1" in the denominator of "5 choose 3" is the number of 
different orders in which any particular group of three could have 
been chosen.

Now the "5*4*3" in the numerator of "5 choose 3" represents the number 
of ways to choose 3 out of 5 if order is important; and the "3*2*1" in 
the denominator represents the number of different orders in which any 
particular group of 3 could have been chosen. The fraction with 
"5*4*3" in the numerator and "3*2*1" in the denominator thus 
represents the number of different ways of choosing 3 out of 5 if 
order is not important.

In numbers, C(5,3) = (5*4*3)/(3*2*1) = 60/6 = 10. These numbers mean 
that there are 60 ways to order any three of five objects, and for 
each particular group of three there are six ways to order them; so 
the number of distinct groups of three out of five objects is 60 
divided by 6. 

If you go from the definition of C(5,3) as it is usually presented, 
you get

                 5!
    C(5,3) = ---------
              3! * 2!

If you simplify this expression, you then get

                 5!       5*4*3*2*1      5*4*3
    C(5,3) = --------- = ------------ = -------
              3! * 2!    (3*2*1)(2*1)    3*2*1

I personally prefer to think of the definition of C(5,3) as being

              5*4*3
    C(5,3) = -------
              3*2*1

because this definition shows me the "5*4*3" in the numerator, which 
is the number of ways to choose 3 out of 5 if order is important, and 
it shows me the "3*2*1" in the denominator, which is the number of 
ways in which any particular group of 3 could have been chosen.

For a final quick review of what I have presented above, here is my 
thinking when I want to find the value of "9 choose 4":

C(9,4) = number of ways to choose 4 out of 9

         number of ways to choose 4 out of 9 if order is important
       = ---------------------------------------------------------
           number of different orders to choose each group of 4

         (four factors starting with 9 and decreasing by 1 each time)
       = ------------------------------------------------------------
         (four factors starting with 4 and decreasing by 1 each time)

          9*8*7*6
       = ---------
          4*3*2*1

And one more example, without all the words, just showing the numbers:

          10*9*8*7*6*5*4
C(10,7) = --------------
           7*6*5*4*3*2*1

I hope all this helps.

Write back if you have any more questions on this topic.

- Doctor Greenie, The Math Forum
  http://mathforum.org/dr.math/