Imagine a grid of six north-south lines, and six east-west lines. You want to walk along the lines of the grid from the south-west corner ($A$) to the north-east corner ($B$) in the shortest way possible, so without any walking back west or south. One possible path through the grid is shown below. How many different paths are there?
If I didn’t have any ideas for how to work this out, I might start by writing down some possible paths. Maybe I could write an n for a step north, and an e for a step east, so the path shown in the diagram would be enneeennne. If I were going to use systematic counting I might start at nnnnneeeee, then nnnneneeee, nnnneeneee, and so on, but it’s too many to list out.
There are a couple ways we could think about this problem. One is that there are ten steps, five of which have to be to the north, and the rest to the east, so we have to choose five of them to be north. Therefore, the number of different paths is ten choose five: \begin{align*} \begin{pmatrix}10\\5\end{pmatrix} &= \frac{10\times9\times8\times7\times6}{5\times4\times3\times2\times1}\\ &= 252. \end{align*} (It’s easy to work this out without a calculator by cancelling common factors, for example the $10$ on the top with the $2$ and $5$ on the bottom.)
Or we could consider the question to be equivalent to how many rearrangements there are of the letters nnnnneeeee. Ten letters, with two sets of five repeats, which makes \begin{align*} \frac{10!}{5!5!} &= \frac{10\times9\times8\times7\times6}{5\times4\times3\times2\times1}\\ &= 252. \end{align*}
Another approach would be to think ‘‘working out the number of paths to $B$ is too hard; let’s start with an easier problem, like working out the number of paths to some of the points closer to $A$’’. So we start writing the number of paths to each point on the grid: Now coming to point $C$, all paths to $C$ must pass through either the point just to the south or the point just to the west. There’s $1$ way to get to the point south of it, and $2$ ways to get to the point west of it, so the number of paths to $C$ must be $2+1$. Now we start to see the pattern: the number of paths to each point is the sum of the number of paths to the south and west. We can easily fill out the whole grid in this way: And we get an answer of $252$ paths to $B$, as before. You might recognise this pattern of numbers as Pascal’s triangle, with the top of the triangle at $A$.