Buying Doughnuts

Date: 03/22/2002 at 22:24:18
From: Wendy
Subject: Probability

I understand the question but I'm stuck on the equations. I know we 
can guess and test to find out, but I was just wondering if there is a 
formula/equation we can use for this question.

Janine wants to buy three doughnuts, and there are five varieties to 
choose from. She wants each doughnut to be a different variety. How 
many combinations are there?

Date: 03/23/2002 at 11:23:34
From: Doctor Ian
Subject: Re: Probability

Hi Wendy,

Let's call the different kinds of doughnuts A, B, C, D, and E.  There 
are 5 ways that Janine can make her first choice:

  A _ _
  B _ _
  C _ _
  D _ _
  E _ _

In each case, there are 4 ways to make the next choice:

  A _ _    A B _
           A C _
           A D _
           A E _

  B _ _    B A _
           B C _
           B D _
           B E _

  C _ _    C A _
           C B _
           C D _
           C E _

  D _ _    D A _
           D B _
           D C _
           D E _

  E _ _    E A _
           E B _
           E C _
           E D _

   5       5*4


In each case, there are three ways to make the final choice. I'm not 
going to list all of them, but you can see the the total number of 
choices will be 5*4*3, right?   

In general, if you have N things, and you want to choose K of them, 
there are 

  N * (N-1) * ... * (N-K+1)

ways to make those choices. If you're going to choose all the items 
eventually, this becomes

  N * (N-1) * ... * 2 * 1

which is abbreviated N! (pronounced N factorial). 

Note that 

                              N * (N-1) * ... * (N-K+1) * (N-K) * ... * 1
  N * (N-1) * ... * (N-K+1) = -------------------------------------------
                                                          (N-K) * ... * 1

because the stuff at the end cancels out.  So we can write

                                N! 
  N * (N-1) * ... * (N-K+1) = ------
                              (N-K)!

You may have to look at this for a while, and work out a few examples 
before it really sinks in, but believe me, if you do that it will be 
time well spent! I strongly recommend that you do it while you have 
time to experiment, rather than when you won't, for example, during a 
test.

Anyway, this tells us the number of 3-doughnut PATTERNS that we can 
make.  But is there really a difference between ABC and CBA? In some 
cases, it makes a difference (for example, if we're generating locker 
combinations); but in our case, it does not. So we need to find some 
way to ignore the duplicates, a way that is easier than looking 
through the list to find them.  

Here's one way to do that. Let's think about doughnuts A, B, and C.  
Given the way we produced the patterns, we're going to have these 
three doughnuts show up in every possible order.  Do you see why?  

Well, how many orders would that be? Do you see that it's really the 
same problem we just solved? The number of patterns that we can make 
from three doughnuts is 3! . So for each combination of three 
doughnuts, we're going to have 3! patterns of those doughnuts. Which 
means that we have 3! times more patterns than we need. 

So to get the number of combinations, we divide the number of patterns 
by this 'excess factor', to get a general formula for the number of 
sets of K elements you can choose from N candidates:

       N!
     ------
     (N-K)!
  ------------
       K!

which can be written more simply as

        N!
     --------
     K!(N-K)!

So if there are 8 types of donuts, and she wants to choose 5, Janine 
could do that in 

     8!      8 * 7 * 6 * 5 * 4 * 3 * 2 * 1
  -------- = --------------------------------------------
  5!(8-5)!              (5 * 4 * 3 * 2 * 1) * (3 * 2 * 1)


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


           = 56 

different ways.

Does this help? 

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