Counting > Pascal's triangle
1234Pascal's triangle

Theory

In the figure you see a 5 by 3 grid. In each grid you have a choice: you can choose "north" or "east".
You can count the number of paths without detours between the point at the bottom left and the top right.
Each path (starting at the left bottom without detour) can be written as a series of 8 letters like ENEENENE, with 3 times "N" and 5 times "E".

To find the number of paths to a point you can add the number of paths to the points below and to the left. Said differently: it is the sum of the number of paths to the possible previous points.
This is easy to check when you realise you can only move up or to the right over the gridlines.
This counting pattern is known as Pascal's triangle.

Another way to determine the number of paths in this grid is to use combinations.
You need to pick 3 out of 8 positions for an N. The order of the 3 N's within the sequence is not relevant (and neither is the order of the E's). Each path with 3 E's and 5 N's is a good path.
You find ( 8 3 ) = 56 possible paths.

previous | next