A good way to count a hard set is to match its objects one-to-one with strings, and strings are easy to count. Grid paths are the classic example, and they explain the identities of Pascal's triangle.
Idea clave
A shortest path from $(0, 0)$ to $(m, n)$ along grid lines, moving right (R) or up (U), is the same thing as a string of $m$ R's and $n$ U's. So there are $\binom{m+n}{n}$ such paths. Paths through a point: multiply the paths to it by the paths from it.
Por qué funciona
Every shortest path uses exactly $m$ right steps and $n$ up steps, in some order, and every such order traces a different path. This is a bijection between paths and strings, so the counts are equal. A string of length $m + n$ is decided by choosing which $n$ of the positions are U's: $\binom{m+n}{n}$. Through a point $P$, a path is a first half (to $P$) followed by a second half (from $P$), and any first half fits any second half: that is the product rule.
Worked examples
Ejemplo resuelto: Counting paths
How many shortest paths go from the bottom-left to the top-right corner of a grid $4$ blocks wide and $3$ blocks tall?
- Each path is a string of $4$ R's and $3$ U's: $7$ steps.
- Choose where the $3$ U's go: $\binom{7}{3} = 35$.
Respuesta: $35$
Ejemplo resuelto: Through a point
In the same grid, how many shortest paths pass through $(2, 1)$?
- To $(2, 1)$: $2$ R's and $1$ U, $\binom{3}{1} = 3$ paths.
- From $(2, 1)$ to $(4, 3)$: $2$ R's and $2$ U's, $\binom{4}{2} = 6$ paths.
- Multiply: $3 \cdot 6 = 18$.
Respuesta: $18$
Ejemplo resuelto: Avoiding a point
In the same grid, how many shortest paths avoid $(2, 1)$?
- All paths minus the paths through it: $35 - 18 = 17$.
- Check with the grid counts: set the count at $(2, 1)$ to $0$ and add up again from the corner; the far corner gets $17$.
Respuesta: $17$
Error común
Counting squares, or adding the two halves. A grid $4$ blocks wide has $5$ vertical lines, but a path takes only $4$ steps to the right; counting the squares or the lines instead of the steps gives the wrong string length. And paths through a point are (paths to it) times (paths from it), not plus. Check: the string must have exactly as many R's as the width and as many U's as the height.