Problem:
Suppose you have an equilateral triangle divided into 9 smaller equilateral triangles as shown, with the bottom side horizontal. Starting from the top corner labeled , you must walk to the bottom right corner labeled , and are only allowed to take steps along the edges down to the left, down to the right, or horizontally to the right. Determine the number of possible paths.
Solution:
The number of paths from the top vertex to itself or to any vertex on the left side of the triangle is . For each other vertex, the number of paths can be found by adding the number of paths to the vertex directly to its left and to the two vertices above it. Thus, the following triangle of numbers tells us the number of paths to each vertex, where each number represents a vertex:
The bottom right number is , so the number of paths to the bottom right corner is .