Path Counting

Combinatorics Progress

Completed0/11

0 completed0 in progress

Path Counting

Counting the number of unique paths on a grid.

Authors: Jaden Park, Leo Zhang

Introduction

Path Counting, also known as Block Walking, is a common problem in combinatorics that involves finding the number of unique paths from one corner of a grid to another, typically under certain restrictions. The most common scenario is finding the number of ways to move from the top-left corner to the bottom-right corner of a grid, moving only down or to the right at each step.

Here is a classic problem.

Example

Imagine a grid of $m \times n$ grid where $m$ is the number of rows and $n$ is the number of columns. You start at the top-left corner and want to reach the bottom-right corner. At each step, you can only move either right or down. How many unique paths are there?

Solution

The key to solving this problem lies in understanding that each path is a sequence of right and down moves. For a grid of size $m \times n,$ you must take exactly $m - 1$ down moves and $n - 1$ right moves to reach the destination, no matter the path taken.

The problem, therefore, reduces to determining in how many ways you can arrange these $m - 1$ down moves and $n - 1$ right moves. This is a permutation problem with a twist: since the moves of the same type are indistinguishable (all right moves are the same, and all down moves are the same), we use combinations instead of permutations.

Formula

The number of unique paths is given by the combination formula:

\textrm{Number of paths} = {{m + n - 2} \choose {m - 1}} = \frac{(m + n - 2)!}{(m - 1)!(n - 1)!}

Here's another example to understand the formula

Example

For a $3 \times 3$ grid, we have $2$ down moves and $2$ right moves t make. Applying this formula gives us:

\textrm{Number of paths} = {{4} \choose {2}} = \frac{4!}{2!2!} = 6

We calculate all the ways you can interleave the down adn right moves. By selecting which of the total $m + n - 2$ steps will be down (or right), you automatically determine the sequence of moves.

Obstructions or Obstacles

When there are obstacles blocking a path, you simply pretend that it's the same grid with no obstacles and then subtract the number of paths that pass through that obstacle.

Here's a practice problem.

Practice Problem

Given this grid, count the number of paths from the top left corner to the bottom right corner given that you can only go down or right.

Final Notes and Tips

Not super common, especially on harder contests, but I would still understand formula. (Memorizing isn't really necessary because you can derive it easily)
When you plot out the different number of paths on a rectangular grid, its diagonal creats pascal's triangle.

Distinguishability

Combinatorics Progress

Counting

Principles

Miscellaneous

Introduction

Example

Solution

Formula

Example

Obstructions or Obstacles

Practice Problem

Final Notes and Tips

Introduction

Example

Solution

Formula

Example

Obstructions or Obstacles

Practice Problem

Final Notes and Tips