Problemas de Conteo de Caminos

Un problema de conteo de caminos consiste en encontrar cuantas rutas distintas existen para ir de un punto de inicio a un punto final, cuando el recorrido se hace a traves de una serie de pasos, decisiones o intersecciones. Estos problemas aparecen al contar rutas en un mapa, trayectorias en una cuadricula, o secuencias de decisiones representadas en un diagrama de arbol.

La idea clave es que casi todo problema de conteo de caminos se puede reducir a aplicar el principio fundamental de conteo: si un camino se construye en varias etapas independientes, y la etapa 1 tiene \( n_1 \) opciones, la etapa 2 tiene \( n_2 \) opciones, y asi sucesivamente hasta la etapa \( k \), entonces el numero total de caminos distintos es:

\( \)Total de caminos\( = n_1 \times n_2 \times \cdots \times n_k \)

Cuando el numero de etapas es pequeno, un diagrama de arbol permite ver cada rama posible sin perder ningun caso. Cada nivel del arbol representa una etapa del camino, y cada rama representa una opcion disponible en esa etapa. El numero total de caminos es simplemente el numero de ramas finales del arbol, lo cual coincide con el resultado del principio fundamental de conteo.

En este ejemplo hay 3 opciones para llegar a una parada de autobus y, desde cada parada, 2 rutas distintas hacia la escuela. El diagrama de arbol tiene 6 ramas finales, y el calculo confirma que \( 3 \times 2 = 6 \) caminos son posibles, sin necesidad de dibujar el arbol completo para numeros mas grandes.

Otro tipo muy comun de problema de conteo de caminos ocurre en una cuadricula, donde solo se permite moverse hacia la derecha o hacia arriba para ir de un punto A a un punto B. Cada camino posible es una secuencia de movimientos, por ejemplo "derecha, derecha, arriba, derecha, arriba".

Para llegar de A a B en la cuadricula anterior se necesitan siempre 3 movimientos hacia la derecha y 2 movimientos hacia arriba, sin importar el orden en que se hagan. El numero de caminos distintos es el numero de formas de acomodar esas 5 letras (3 "derecha" y 2 "arriba") en una fila, que es exactamente una combinacion:

\( \binom{5}{2} = \dfrac{5!}{2! \, 3!} = \dfrac{120}{2 \times 6} = 10 \)

Por lo tanto, existen 10 caminos distintos posibles de A a B. En general, para una cuadricula que requiere \( m \) movimientos hacia la derecha y \( n \) movimientos hacia arriba, el numero de caminos es:

\( \binom{m+n}{m} = \dfrac{(m+n)!}{m! \, n!} \)

No todos los problemas de conteo de caminos se resuelven igual, y reconocer la estructura del problema es la parte mas importante:

• Si cada etapa del camino tiene un numero fijo de opciones distintas entre si, multiplica las opciones de cada etapa con el principio fundamental de conteo.
• Si el numero de etapas es pequeno y quieres visualizar cada ruta, dibuja un diagrama de arbol.
• Si el camino es una secuencia de movimientos repetidos (como derecha y arriba) donde el orden entre movimientos iguales no importa, usa una combinacion en lugar de una permutacion.

Una red de senderos conecta un campamento con un mirador pasando por 4 cruces intermedios. Desde el campamento hay 2 senderos hacia los cruces, y desde cada cruce hay 3 senderos distintos hacia el mirador. ¿Cuantos caminos totales existen del campamento al mirador?

Aqui el camino tiene dos etapas: elegir un cruce (2 opciones) y elegir un sendero final desde ese cruce (3 opciones). Aplicando el principio fundamental de conteo:

\( 2 \times 3 = 6 \) caminos posibles del campamento al mirador.

Related lessons

• Es Statistics Help