Given a square grid consisting of nodes and edges, starting from the top left corner node how do you calculate the number of paths to the node in the bottom right corner while only being able to move down and to the right? For instance in a 1x1 grid there would be 2 paths, in a 2x2 grid there would be 6 and so on.

- Log in to post comments

1 answer

One approach is to notice - after some trial and error - that the number of paths at each node is represented by the equivalent entry in Pascal's triangle. So in general for a NxN grid one would construct Pascal's triangle up to height 2N and take the entry in the center position of the last row.

- Log in to post comments