Examples of the Fundamental Counting PrincipleDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/