Una ciudad tiene 4 calles de este a oeste y 4 de norte a sur, formando una cuadrícula. Una persona parte de la esquina noroeste A y camina hasta la esquina sureste B, y en cada cruce solo se mueve hacia el este o hacia el sur. ¿Cuántas rutas distintas hay?

Step-by-step solution

1. 1

   Cuenta los movimientos que debe hacer cada ruta. Con $4$ calles en cada dirección hay $3$ manzanas en cada dirección, así que toda ruta consta exactamente de

   $3\ \text{movimientos al este}\quad\text{y}\quad 3\ \text{movimientos al sur}$

   para un total de $6$ movimientos, y esto es igual para todas las rutas, que es lo que convierte el conteo en algo puramente combinatorio.

2. 2

   Convierte una ruta en una palabra. Una ruta queda descrita por completo por el orden de sus movimientos, es decir, por una cadena de $6$ letras, tres E y tres S, como $EESESS$. Cadenas distintas dan rutas distintas y toda ruta da una cadena, así que contar rutas = contar cadenas.

3. 3

   Elige las posiciones de los movimientos al este. Una vez que decides cuáles $3$ de las $6$ posiciones llevan una E, las S rellenan el resto. El número de formas es

   $\binom{6}{3}$

4. 4

   Evalúa el coeficiente binomial.

   $\binom{6}{3}=\frac{6!}{3!\,3!}=\frac{6\cdot 5\cdot 4}{3\cdot 2\cdot 1}=20$

   $\boxed{20\ \text{rutas}}$

5. 5

   Comprueba con el triángulo de Pascal sobre la cuadrícula. Etiqueta cada cruce con el número de rutas que llegan a él desde $A$: la fila superior y la columna izquierda valen todas $1$, y cualquier otro nodo es la suma del nodo de arriba y el nodo de su izquierda. Así se construyen las filas $1,1,1,1$ / $1,2,3,4$ / $1,3,6,10$ / $1,4,10,20$, y la esquina $B$ lleva $20$ ✓, lo que coincide con el conteo binomial.