Drexel dragonThe Math ForumDonate to the Math Forum

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

Examples of the Fundamental Counting Principle


Date: 02/17/2001 at 12:00:47
From: Diana
Subject: The Counting Principle and Tree Diagrams

I have a math problem that I can't figure out. I tried making a tree 
diagram but it makes no sense. I would really appreciate it if you can 
show me how to answer this question. The problem is:

There are three ways to go from Town A to Town B. There are four 
ways to go from Town B to Town C. How many different ways are there 
to go from Town A to Town C, passing through Town B?

Thank you very much.


Date: 02/19/2001 at 12:01:50
From: Doctor Ian
Subject: Re: The Counting Principle and Tree Diagrams

Hi Diana,

Here is a way to think about this. There are three ways to go from 
town A to town B.  We can write those paths down:

     AB
     AB'
     AB"

Now, once we've started on path AB, there are four ways to get to 
town C. We can write those paths down:

     ABC
     ABC'
     ABC"
     ABC^

But there are also four paths through AB':

     AB'C
     AB'C'
     AB'C"
     AB'C^

And there will be four more paths through AB". I'll let you write 
them down. 

So that gives us 12 total paths. How does this relate to the 
Fundamental Counting Principle? Here is where trees are useful. We 
can draw a tree to represent all the possible paths from A to C 
through B. We start by creating nodes for the first choice:

                        A
                /       |        \
               B        B'        B"

Note that there were three choices, and we have three paths. We then 
create nodes for the next choice:

                                A
                /               |                \
               B                B'                B"
           /  / \  \        /  / \  \         /  / \  \
          C  C'  C" C^     C  C'  C" C^      C  C'  C" C^


Look at what happened. There were four possible choices, and the 
number of paths increases by a factor of 4.  

If you draw a tree in which each level represents one choice with N 
alternatives, then each time you make a choice you increase the 
number of possible outcomes by a factor of N. The Fundamental 
Counting Principle tells you that you can compute the number of paths 
without going to the trouble of drawing the tree, just by multiplying 
the number of alternatives at each step.  

In your problem, you start from A. You have only one alternative, so 
the number of possible outcomes so far is 1. You then choose from 
three alternatives for going to B.  So now the number of possible 
outcomes is 1*3, or 3.  

You then choose from four alternatives for going to C. So now the 
number of possible outcomes is 3*4, or 12. (That is, for _each_ of 
the three outcomes of the previous step, there are four _new_ 
outcomes.)

Sometimes it's easier to think in terms of copies, rather than paths. 
Suppose you want to draw some faces. You can start by drawing the 
outline of a face. You now have one drawing. You'd like to try three 
different kinds of noses, so you make three copies of the outline, and 
draw a different kind of nose on each one. Now you have three 
drawings.  

     +--------+ +--------+ +--------+
     | Nose 1 | | Nose 2 | | Nose 3 |
     +--------+ +--------+ +--------+

Next, you'd like to try four different kinds of eyes. You make four 
copies of each drawing, and draw each kind of eyes. So that gives you 
twelve drawings.  

     +--------+ +--------+ +--------+
     | Nose 1 | | Nose 2 | | Nose 3 |
     | Eyes 1 | | Eyes 1 | | Eyes 1 |
     +--------+ +--------+ +--------+
     +--------+ +--------+ +--------+
     | Nose 1 | | Nose 2 | | Nose 3 |
     | Eyes 2 | | Eyes 2 | | Eyes 2 |
     +--------+ +--------+ +--------+
     +--------+ +--------+ +--------+
     | Nose 1 | | Nose 2 | | Nose 3 |
     | Eyes 3 | | Eyes 3 | | Eyes 3 |
     +--------+ +--------+ +--------+
     +--------+ +--------+ +--------+
     | Nose 1 | | Nose 2 | | Nose 3 |
     | Eyes 4 | | Eyes 4 | | Eyes 4 |
     +--------+ +--------+ +--------+

Next, you'd like to try two different kinds of hair. You make two 
copies of each drawing, and draw each kind of hair. So that gives you 
twenty-four drawings. 

     +--------+     +--------+ +--------+
     | Nose 1 | =>  | Nose 1 | | Nose 1 |
     | Eyes 1 |     | Eyes 1 | | Eyes 1 |
     +--------+     | Hair 1 | | Hair 2 |
                    +--------+ +--------+

(I'm not going to draw all of them!)

Every time you want to try something that has N alternatives, you 
have to make N copies of _all_ the drawings you already have. Which 
means that if you have K drawings already, you will end up with N*K 
drawings. 

In this case, you end up with 

     1 outline * 3 nose choices * 4 eye choices * 2 hair choices

       = (1 * 3 * 4 * 2) different drawings

I hope this helps. Write back if you'd like to talk about this some 
more, or if you have any other questions. 

- 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

[Privacy Policy] [Terms of Use]

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

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/