Benefits of Pascal’s Triangle: Number of Ways to Traverse a Graph

I came across a problem today on AlgoExpert, titled the Number of Ways to Traverse a Graph (available on leetcode as well). Essentially, given a graph with width and height, how many possible unique paths are there to get from the top left to bottom right by only moving down and right?

For example, given a 2x3 matrix, there are 3 unique paths: [down, right, right], [right, down, right], [right, right, down].

We could solve this one using recursion and force the matrix down to a one by one, this would likely end up with a Big O of 2^(width+height).

Next level programming tells us to use dynamic programming where we create a table and build up to width x height, calculating the next row based on the previous row. This would likely allow us to cut the time to Big O of (width*height).

If you want to be clever though, let me introduce you to a guy named Pascal who brought about one of the greatest triangles ever. Pascal’s Triangle is built up by each number being the sum of the two numbers above it. See image below:

Pascal’s triangle has many uses to it, most commonly is if you were to take (x+y)^n, we can get the coefficients for the output by going across the nth row(first row is the 0th row), while increasing the x exponent and decreasing the y exponent. So (x+y)⁴ is 1x⁴y⁰ + 4x³y¹ + 6x²y² + 4x¹y³ + 1x⁰y⁴. That is just the tip of the iceberg, here is a great resource for some of the phenomenal uses of Pascal’s Triangle: https://medium.com/i-math/top-10-secrets-of-pascals-triangle-6012ba9c5e23

Now back to the problem at hand. If we think about the problem starting with the end location, there are two options to get to the last cell in a graph, either come from above or come from the left. So if we examine a 3x3 grid, we can move down from 2x3 grid or move right from a 3x2 grid. So the total combinations for a 3x3 grid would be the sum of both a 3x2 and 2x3, which are both 3 paths, which gives us 6 total paths. We can use this information to build up a table of possibilities given various row and column lengths for each cell, you can get the number by adding the cell to the left to the cell above.

Now take a closer look at this, notice something familiar? If you are having trouble, try rotating the table 45 degrees. What we have here is Pascal’s triangle! See below:

This will let us ignore recursion and dynamic methods and solve this much faster. Let’s call the minimum dimension “k” (actually minimum-1 to be exact), the solution would be the kth item in row “n” of pascals triangle, where n is height + length-2, to get to the kth item in a row in pascals triangle, we can use the Combination formula:

This is not the most efficient formula however since factorial functions have Big O(n) run time. Using it would give us a run time O(width + height), an improvement but still not the best. Another way to get the result is to traverse across the row of pascals triangle. To do that we can multiply continually by (n-k)/(k+1) as k increases from 0 to n. So traversing across the 8th row, we start with 1 and multiply by 8/1 to go from 1 to 8, then multiply by 7/2 to get from 8 to 28, then by 6/3 to get form 28 to 56, etc.

Putting this together, we have a final solution below with a Big O(k) where k is the minimum of width and height minus 1.

As demonstrated by the code, Pascal’s Triangle is a beast for solving complex mathematical problems and is worth keeping in your wheelhouse.