Paths to Triangle Points

Date: 05/26/99 at 06:23:22
From: Yael Goldstein
Subject: Pascal's triangle - paths to particular points 

Dear Doctor Math:

We've been given a triangle and within it are rows of equilateral 
triangles. The first row contains one triangle, the second row 
contains three triangles, the third row - five, fourth - seven, etc.

We have been asked to find the maximum number of paths that can be 
taken to reach each vertex of each of the triangles. Beginning from 
the top of the triangle, we can only move down or along (not up) the 
lines of all the little triangles to each point. By a process of trial 
and error we have worked out that there are two paths to to each point 
of the triangle in the first row, and eight paths to the points on the 
second row of triangles, but once we reached the third row of 
triangles we found it too difficult to count the number of paths. We 
believe that Pascal's triangle is involved. Could you please help?

Yours sincerely, 
Yael Goldstein

Date: 05/26/99 at 08:06:23
From: Doctor Anthony
Subject: Re: Pascal's triangle - paths to particular points 

This problem comes under the general heading of Permutations and 
Combinations. The number of paths by which you could arrive at a 
particular point in, say, the 6th row is the number of ways that you 
can string together Left and Right moves such that you end up at that 
point. 

Suppose we have made a total of 4 moves along the righthand branches 
and 2 moves along the lefthand branches. This will bring us to a 
particular point in the 6th row, and we could arrive there in a 
variety of ways, the total number of ways being the number of ways 
that you could arrange 4 R's (for right) and 2 L's (for left).

                                  6!
  Number of different routes = -------- =  15
                                 4! 2!

There is a symbol for this value  C(6,4) which is the number of 
combinations of 4 things that can be made from 6 different things.  It 
is also, of course, the number of combinations of 2 things that can be 
made from 6 things, since every time you make up a group of 2 things 
there will be a group of 4 things left over.

   So C(6,4) = C(6,2) = 15 [Most calculators will have this function].

If you want the total routes for all points in the 6th row we have two 
choices (right or left) for each step on the way giving  2^6 = 64 as 
the total of all routes. If C(n,r) represents the number of right 
branches you take in n steps then, with n = 6 we get

  C(6,0) + C(6,1) + C(6,2) + C(6,3) + C(6,4) + C(6,5) + C(6,6)
 
 =    1  +    6   +   15   +   20    +   15   +   6    +   1

 =   64    as we found above. 

You will find that the numbers 1, 6, 15, 20, 15, 6, 1 are indeed the 
entries in the 6th row of Pascal's triangle.  So if you want to find 
the number of routes to each point in your diagram you simply read off 
the appropriate row of Pascal's triangle.

- Doctor Anthony, The Math Forum
  http://mathforum.org/dr.math/