El siguiente diagrama muestra una matriz de $4$ filas y $4$ columnas. Enumeremos las filas de arriba hacia abajo, y a las columnas de izquierda a derecha. Denotaremos la celda que está en la fila $r$ y columna $c$ usando un par ordenado $(r, c)$. Al igual que en el plano cartesiano, empezaremos la enumeración empezando desde $0$. Por ejemplo, la celda amarilla está codificada por el par $(1, 2)$.

1	1	1	1
1	2	3	4
1	3	6	10
1	4	10	20

Hay hay un ratón en la celda $(0, 0)$ que quiere viajar hasta la celda $(3, 3)$. En un movimiento, el ratón puede decidir moverse una columna hacia la derecha, o una fila hacia abajo. Más formalmente, si el ratón está en la celda $(r, c)$, este puede moverse hacia la celda $(r, c + 1)$ o hacia $(r + 1, c)$, siempre que tal celda exista. Por ejemplo, si el ratón está en la celda amarilla $(1, 2)$ entonces puede moverse hacia la derecha $(1, 3)$ o hacia abajo $(2,2)$.

¿De cuántas formas puede realizar su viaje el ratón?

Observa que hay una sola forma de llegar a las celdas de la primera fila (solo podemos llegar a tales celdas moviéndonos siempre hacia la derecha). Similarmente, hay una única forma de llegar a las celdas de la primera columna (solo podemos llegar a tales celdas moviéndonos siempre hacia abajo).

Denotemos por $F(r, c)$ al número de formas en las que el ratón puede llegar a la celda $(r,c)$. Con esta notación, la afirmación del parrafo anterior se resume a $F(0, x) = F(x, 0) = 1$ para cualquier $x$ válido.

Para llegar a la celda celeste $(1, 1)$, anteriormente el ratón debió estar una celda hacia la izquierda $(1, 0)$ o una celda hacia arriba $(0, 1)$. Por tanto $F(1, 1) = F(1, 0) + F(0, 1) = 1 + 1 = 2$. Similarmente con la celda amarilla $F(1, 2) = F(1, 1) + F(0, 2) = 2 + 1 = 3$. Con esta idea podemos calcular el número de formas en las que puede el ratón llegar a cada celda.

Más generalmente, la única forma en la que el ratón puede llegar a la celda $(x, y)$ es dando un paso hacia abajo desde $(x-1, y)$ o dando un paso a la derecha desde $(x, y - 1)$. Por tanto, $F(x,y) = F(x-1, y) + F(x, y-1)$. A este tipo de ecuaciones se les llama recurrencias, calculamos el valor de cierta función a partir de valores calculados anteriormente.

Los movimientos del ratón pueden ser codificados con una cadena de 6 caracteres, por ejemplo DAADDA significa que primero el ratón se movió hacia la derecha, después dos veces hacia abajo, luego dos veces hacia la derecha y finalmente una vez hacia abajo.

Cualquier cadena de seis letras que tenga $3$ letras D y $3$ letras A (en cualquier orden) representa una forma de movimiento para el ratón. De las seis posiciones disponibles, tenemos que seleccionar 3 en las cuales pondremos caracteres D, y en el resto caracteres A. El número de formas de realizar esto es $\binom{6}{ 3}$.

Más generalmente, si el ratón quiere llegar a la celda $(r,c)$, entonces tiene que dar $r$ pasos hacia abajo y $c$ hacia la derecha, por tanto su movimiento está codificado por una cadena de $r+c$ letras, de las cuales tenemos que escoger $r$ posiciones para poner la letra A y en las $c$ posiciones restantes la letra D. Esto se puede hacer de $\binom{r+c}{r}$ formas.

Se observa que hay una relación entre la recurrencia que calulemos anteriormente $F$ y las combinatorias binomiales. De hecho si rotamos 45 grados a la tabla inicial ¡obtenemos el triángulo de Pascal! Las recurrencias de las combinatorias son similares $\binom{x}{0}=\binom{x}{x}=1$, $\binom{x}{y}=\binom{x}{y-1} + \binom{x-1}{y}$.