Elementary Foundations: An introduction to topics in discrete mathematics

Consider paths in the $5\times 10$ grid below that start at the bottom left and end at the top right, and only move up or right at each step. (One such path is drawn in.) How many such paths are there?

Let $P$ represent the set of all such paths. We can distinguish each element of $P$ by the sequence of directions it takes at each step. Let $\mathrm{\Sigma }=\{R,U\}\text{,}$ where $R$ and $U$ stand for the directions “right” and “up”, respectively. Then for each path $p\in P$ we can build a word $w_p\in {\mathrm{\Sigma }}^{\ast }$ by setting the letters of $w_p$ to correspond to the steps in the path. For example, the path in the diagram above would correspond to the word $RRURUURRRRURR\text{.}$

This assignment of words in ${\mathrm{\Sigma }}^{\ast }$ to paths in $P$ is a function! Let’s call it $f:P\to {\mathrm{\Sigma }}^{\ast }\text{,}$ and set $W=f(P)\text{,}$ the image of $f$ in ${\mathrm{\Sigma }}^{\ast }\text{.}$ This function is clearly one-to-one, as different paths must produce different words of direction indicators. And since every function maps its domain surjectively onto its image, we obtain a bijection $f:P\to W$ by restricting the codomain. Therefore, we can count the paths in $P$ by instead counting the words in $W\text{!}$