Unipal Initiative - Free Competition Math Courses, From Students For Students

Basic lattice paths

A path from $(0,0)$ to $(m,n)$ using only unit steps right and up requires exactly $m$ right-steps and $n$ up-steps, in some order — so the count is just the number of ways to arrange that sequence of steps:

\binom{m+n}{n}

Paths around a blocked point

To count paths that avoid a blocked square, use the complement: count all paths to the destination, then subtract the paths that pass through the blocked point. The number of paths through a specific point splits into two independent legs — start to blocked point, blocked point to destination — multiplied together:

\text{paths through } P = \binom{\text{steps to } P}{\cdots} \times \binom{\text{steps from } P \text{ to end}}{\cdots}

With multiple blocked squares, this becomes an inclusion-exclusion problem: subtract paths through each blocked point, add back paths through pairs of blocked points (double-subtracted), and so on.

Diagonal-move paths

If diagonal moves are allowed alongside right/up moves, there's no clean closed form — instead, build up the count recursively, since the number of paths to a cell equals the sum of paths to the three cells that could step into it:

a_{i,j} = a_{i-1,j} + a_{i,j-1} + a_{i-1,j-1}

Worked example

Problem: How many paths from $(0,0)$ to $(4,4)$ (right/up steps only) avoid passing through $(2,2)$ ?

Solution: Total paths: $\binom{8}{4}=70$ . Paths through $(2,2)$ :

\binom{4}{2} \times \binom{4}{2} = 6 \times 6 = 36

Paths avoiding $(2,2)$ : $70 - 36 = 34$ .

Practice problems

1.How many lattice paths are there from $(0,0)$ to $(3,5)$ using only right and up steps?

2.How many paths from $(0,0)$ to $(5,5)$ pass through the point $(2,3)$ ?

3.How many paths from $(0,0)$ to $(6,6)$ avoid the point $(3,3)$ ?

4.How many paths from $(0,0)$ to $(2,2)$ use only right, up, and diagonal (up-right) unit steps?

Grid Paths

Basic lattice paths

Paths around a blocked point

Diagonal-move paths

Practice problems