Paths to Triangle PointsDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/