Usar diagramas de árbol para contar paso a paso.
Los árboles de conteo, que seguido llamamos diagramas de árbol, son representaciones visuales que usas en combinatoria para organizar y enumerar los resultados de una secuencia de eventos o elecciones. Un diagrama de árbol empieza con un solo punto de partida (la raíz) y se ramifica en las opciones posibles para el primer evento. Desde el final de cada rama (nodo), brotan nuevas ramas que representan las opciones para el siguiente evento. Este proceso sigue hasta que agotas todas las elecciones secuenciales. Los puntos finales de las últimas ramas, conocidos como "hojas", representan los resultados distintos y completos de la secuencia.
Esta técnica es fundamental porque te da un puente concreto entre enlistar a mano (fuerza bruta) y las fórmulas algebraicas abstractas (el Principio de la Multiplicación). Aunque los métodos algebraicos son más rápidos para números grandes, los diagramas de árbol son mejores para problemas que involucran eventos dependientes —donde las opciones disponibles en un paso posterior dependen de la elección específica que hiciste en un paso anterior. Te permiten visualizar la estructura del problema, asegurando que no se te pase ningún caso y que no cuentes nada dos veces.
La idea clave de los árboles de conteo es la naturaleza recursiva del conteo. Al dividir un problema complejo en una jerarquía de subproblemas más pequeños y manejables, puedes manejar condiciones irregulares (como "si pasa A, entonces B tiene 2 opciones; pero si pasa C, B tiene 3 opciones") que las fórmulas estándar de permutaciones no pueden resolver fácilmente. Una vez que construyes el árbol, el número total de resultados es simplemente el conteo de las hojas, o la suma de los productos a lo largo de cada camino distinto.
1. El Principio de la Multiplicación (Ramificación Uniforme) Si un árbol tiene $k$ niveles (etapas), y en cada nodo del nivel $i$ hay exactamente $n_i$ ramas, el número total de hojas $N$ es el producto de los factores de ramificación: $$N = n_1 \times n_2 \times \dots \times n_k = \prod_{i=1}^{k} n_i$$
2. La Regla de la Suma (Ramificación Irregular) Si el número de opciones depende del camino que tomes, el número total de resultados es la suma de los resultados de los casos disjuntos definidos por la primera rama. Si la raíz se divide en eventos disjuntos $E_1, E_2, \dots, E_m$, entonces: $$|S| = |E_1| + |E_2| + \dots + |E_m|$$ donde $|E_i|$ representa el número de hojas generadas a partir de la rama $E_i$.
3. Probabilidad de Camino (Para Árboles Ponderados) En contextos de probabilidad, si cada rama tiene una probabilidad asociada $P_i$, la probabilidad de un resultado específico (hoja) es el producto de las probabilidades a lo largo del camino desde la raíz hasta esa hoja: $$P(\text{resultado}) = P(\text{rama}_1) \times P(\text{rama}_2) \times \dots \times P(\text{rama}_k)$$
Teorema: Para un proceso secuencial con $k$ pasos, si el paso $i$ tiene $n_i$ opciones distintas sin importar las selecciones anteriores, el número total de resultados distintos es $\prod_{i=1}^{k} n_i$.
Demostración por Inducción:
Paso 1: Caso Base Toma $k=1$. El proceso consiste en un solo paso con $n_1$ opciones. El diagrama de árbol consiste en una raíz y $n_1$ ramas, lo que da como resultado $n_1$ hojas. $$N = n_1$$ La fórmula se cumple para $k=1$.
Paso 2: Hipótesis de Inducción Supón que para un proceso con $k$ pasos, con opciones $n_1, n_2, \dots, n_k$, el número total de resultados (hojas) es: $$L_k = n_1 \times n_2 \times \dots \times n_k$$
Paso 3: Paso Inductivo Considera un proceso con $k+1$ pasos. Por la hipótesis de inducción, después de completar los primeros $k$ pasos, tienes $L_k$ puntos finales (nodos) distintos.
Para el paso $(k+1)$, hay $n_{k+1}$ opciones disponibles. En el diagrama de árbol, extiendes cada uno de los $L_k$ nodos existentes agregando $n_{k+1}$ ramas nuevas.
Como las opciones son distintas, no habrá dos caminos que se junten. Por lo tanto, el nuevo número total de hojas $L_{k+1}$ es la suma de las nuevas ramas añadidas a cada nodo existente: $$L_{k+1} = \underbrace{n_{k+1} + n_{k+1} + \dots + n_{k+1}}{L_k \text{ veces}}$$ $$L{k+1} = L_k \times n_{k+1}$$
Sustituye la expresión de $L_k$ de la hipótesis: $$L_{k+1} = (n_1 \times n_2 \times \dots \times n_k) \times n_{k+1}$$ $$L_{k+1} = \prod_{i=1}^{k+1} n_i$$
Conclusión Por el Principio de Inducción Matemática, el número total de resultados para cualquier secuencia finita de elecciones es el producto del número de opciones en cada paso. Esto confirma que las hojas de un árbol de conteo enumeran los resultados totales definidos por el Principio de la Multiplicación.
$\square$