Pathfinding and Pascal's Triangle

TL;DR

You can use Pascal's Triangle to count the number of unique shortest paths on a grid, moving only right or down. Each entry in Pascal's Triangle represents the number of ways to reach that specific point. This method simplifies complex pathfinding problems into a straightforward counting exercise.

1. The Mental Model

Imagine you're walking on a city grid and can only move either right or down. Pascal's Triangle helps you quickly figure out how many different ways you can reach any intersection from your starting point. It's all about counting the possible steps.

2. The Core Material

When you're trying to find the number of paths from one point to another on a grid, with the constraint that you can only move right or down, Pascal's Triangle comes in super handy. Each number in Pascal's Triangle is the sum of the two numbers directly above it. This property perfectly mirrors how paths combine on a grid.

Think about it: to reach any cell (x, y) on a grid, you must have come from either the cell directly to its left (x-1, y) or the cell directly above it (x, y-1). So, the number of ways to reach (x, y) is the sum of the ways to reach (x-1, y) and (x, y-1). This is the exact same rule that generates Pascal's Triangle!

How to Apply It

Photo by Gustavo Fring on Pexels

1. Set up your grid: Start at (0,0). Mark this as your starting point.
2. Initialize the first row/column: If you're on the very top row or very leftmost column, there's only one way to get to any cell there (just keep moving right or just keep moving down). So, all cells in the first row and first column get a '1'.
3. Fill the rest of the grid: For every other cell, the number of paths to reach it is the sum of the number of paths to the cell directly above it and the cell directly to its left.
4. The final answer: The number in the cell you want to reach is your total number of unique paths.

Here's a visual of how paths combine on a small grid:

graph TD
    A["Start (1 way)"] --> B["Right (1 way)"]
    A --> C["Down (1 way)"]
    B --> D["Right (1 way)"]
    C --> D["Right + Down (2 ways)"]
    B --> E["Down (1 way)"]
    C --> E["Down (1 way)"]
    D --> F["Right (1 way)"]
    E --> F["Right + Down (3 ways)"]
    D --> G["Down (2 ways)"]
    E --> G["Down (3 ways)"]
    F --> H["End (3 ways)"]
    G --> H["End (6 ways)"]

Notice how D gets 1 (from B) + 1 (from C) = 2. And F gets 1 (from D) + 2 (from E) = 3. This pattern is identical to Pascal's Triangle.

Connection to Combinations

Photo by Gül Işık on Pexels

This problem is also directly related to combinations. If you need to make R moves to the right and D moves down to reach your destination, the total number of moves will be R + D. The problem then becomes: in those R + D total moves, how many ways can you choose R of them to be "right" moves (or equivalently, how many ways can you choose D of them to be "down" moves)?

The formula for this is the combination formula:
$${n \choose k} = \frac{n!}{k!(n-k)!}$$
Where $n$ is the total number of moves ($R + D$), and $k$ is the number of right moves ($R$) (or down moves, $D$).

So, for a grid that is $R$ units to the right and $D$ units down from the start, the number of paths is:
$${R+D \choose R} \text{ or } {R+D \choose D}$$

3. Worked Example

Let's say you want to find the number of shortest paths from the top-left corner (start) to the bottom-right corner (end) of a 3x2 grid. This means you need to move 3 units right and 2 units down.

1. Grid Visualization:
   Start (0,0) --- (1,0) --- (2,0) --- (3,0) | | | | (0,1) --- (1,1) --- (2,1) --- (3,1) | | | | (0,2) --- (1,2) --- (2,2) --- End (3,2)

2. Applying Pascal's Triangle:
   Start by filling in the '1's along the edges:

   1 1 1 1 1 1

   Now, fill in the rest by adding the number above and to the left:

   1 1 1 1 1 2 3 4 (1+1=2, 1+2=3, 1+3=4) 1 3 6 10 (1+2=3, 3+3=6, 4+6=10)

   The value in the bottom-right corner is 10. So, there are 10 unique shortest paths.

3. Using the Combination Formula:
   You need to move 3 units right (R=3) and 2 units down (D=2).
   Total moves, $n = R + D = 3 + 2 = 5$.
   Number of paths = ${5 \choose 3}$ or ${5 \choose 2}$.

   Let's use ${5 \choose 2}$:
   $${5 \choose 2} = \frac{5!}{2!(5-2)!} = \frac{5!}{2!3!} = \frac{5 \times 4 \times 3 \times 2 \times 1}{(2 \times 1)(3 \times 2 \times 1)} = \frac{120}{2 \times 6} = \frac{120}{12} = 10$$

   Both methods give you the same answer: 10 paths.

4. Key Takeaways

• Pascal's Triangle entries directly correspond to the number of shortest paths to a specific point on a grid.
• Each cell's value is the sum of the values from the cell directly above and the cell directly to its left.
• The first row and first column always start with '1's, as there's only one way to reach any point along those edges.
• This method only works for "shortest paths" where you can only move right or down (or left/up, depending on your start/end).
• The problem can also be solved using the combination formula ${n \choose k}$, where $n$ is the total moves and $k$ is the number of moves in one direction.

Common Mistakes to Avoid:

• Forgetting to start with 1s: The edges of your grid (first row/column) must be initialized with 1s.
• Counting diagonals or backward moves: This method assumes you only move right and down (or equivalent straight lines). Diagonal or backward moves aren't counted.
• Mixing up rows and columns for combinations: Ensure you're consistent with what represents 'R' and 'D' in the combination formula.
• Not understanding "shortest path": Shortest path implies minimal moves. If you can move left/up, there would be infinite paths.
• Calculating for obstacles incorrectly: If there are obstacles, you can't simply sum the paths. You'd mark obstacle cells as '0' and adjust accordingly.

5. Now Try It

You're at the top-left corner of a grid and need to reach a point that is 4 units to the right and 3 units down. Use both the Pascal's Triangle method (drawing out the grid and filling in numbers) and the combination formula to find the number of unique shortest paths.

What success looks like: You get the same answer using both methods, and that answer is 35.