Associated Topics || Dr. Math Home || Search Dr. Math

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/

Associated Topics:
High School Discrete Mathematics
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search