Counting Lattice Paths

Counting Lattice Paths

Suppose that we have the following $7$ by $5$ lattice:

Screen%20Shot%202015-08-19%20at%208.30.20%20AM.png

Further suppose that we start in the bottom left of the lattice at point $P$ and end up at the top right of the lattice at point $Q$.

Screen%20Shot%202015-08-19%20at%208.34.23%20AM.png

How many distinct paths can we make from point $P$ to point $Q$ if we are only allowed to travel north and east. For example, one such path from $P$ to $Q$ is:

Screen%20Shot%202015-08-19%20at%208.33.47%20AM.png

It should be relatively clear that in each path we must travel $4$ north and $6$ east regardless of what path we take. Therefore, we must draw $4 + 6$ strokes each representing a movement of either north or east. Therefore we will start by having $10$ placeholder $*$s:

(1)
\begin{align} \quad * \: * \: * \: * \: * \: * \: * \: * \: * \: * \end{align}

Let $A = \{ n, e \}$ where $n$ represents north and $e$ represents east. We must place an element from $A$ in each of the placeholders such that $n$ is selected $4$ times and $e$ is selected $6$ times.

If $A$ was a $10$-element set and each element could only be used once, then we would have $10!$ different paths. For our problem though, we only have $2$ elements. For the element $n$ we take $10$ positions and choose $4$ which automatically chooses the remaining positions to be $e$. Therefore the total number of paths from $P$ to $Q$ is:

(2)
\begin{align} \quad \binom{10}{4} = \frac{10!}{4!(10-4)!} = \frac{10!}{4! \cdot 6!} = 210 \end{align}

We can generalize this. If we have a point $P$ which we arbitrarily place at the origin, that is $P = (0, 0)$, then to get to the point $Q = (a, b)$ where $a, b \geq 0$ there will be precisely $\displaystyle{\binom{a+b}{a} = \binom{a+b}{b} = \frac{(a + b)!}{a! \cdot b!}}$ different paths moving only north or only east.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License