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
Math Forum Home || Math Library || Quick Reference || Math Forum Search