Associated Topics || Dr. Math Home || Search Dr. Math

### 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

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/
```
Associated Topics:
High School Number Theory
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