Expert: Josh - 3/10/2008

Question
I was wondering how you would show, using tree diagrams, how to see how
many options there are for choosing 3 people out of 5 people?  Basically proving
the formula C(n,r)=n!/r!(n-r)!.

Answer
Hi Ryan,

As I elaborate on how this can be done, it would be useful if you could look at the tree diagram at (http://www.artofproblemsolving.com/Classes/IntroNumbers/L3/exponenttree.gif) so we are on the same page.

Since we have to make 3 selections (pick 3 from 5), we know there will be 3 hierarchical levels in our tree diagram.

Initially, we have to choose one out of five people. The root of the tree will branch off in 5 directions at level 1. You can label these branches with "1","2","3","4","5". The second time, we have to choose one out of four people. So, for each of the four branches emerging from level 1, each will branch off in 4 directions at level 2. From top to bottom, you can label these new branches with "2,3,4,5" (for the parent node 1 at level 1), "1,3,4,5" (for parent node 2 at level 1), "1,2,4,5" (for parent node 3 at level 1), "1,2,3,5" (for parent node 4 at level 1) and "1,2,3,4" (for parent node 5 at level 1).

Notice that the labeling is done without replacement. i.e., if person x already appeared earlier along the branch, it cannot repeat again at a later node.

Now, we have 5x4 nodes at level 2. To choose one person from the three people remaining, each of these nodes will branch off in 3 directions. The labeling is done in an analogous manner, which ensures a number is never repeated along a branch. At level 3, we will see 5x4x3 nodes, or possibilities. But these groups are not distinct. Groups are formed by including the numbers (or labels of people) as you traverse each path from the root node (left most) to the youngest node (right most).
For example, the top path leads to (1,2,3), the next lower path leads to (1,2,4) and so forth.

You will find that the groups can be formed uniquely in  5x4x3x2x1/[(3x2x1)(2x1)] = 10 ways.