Árboles y combinatoria

Objetivos

• Dibujar un árbol y leer el producto.
• Calcular V(n,k) y C(n,k).
• Justificar el cociente k!.

Árbol, variaciones, combinaciones

Cada nivel del árbol es una decisión. Variaciones V(n,k)=n·(n−1)·…·(n−k+1) cuando el orden importa. Combinaciones C(n,k)=V(n,k)/k! cuando no importa: cada grupo se había contado k! veces.

Ejemplo 1 — monedas

Tienes 1 €, 2 € y 5 € (una moneda de cada). ¿De cuántas formas distintas puedes ordenarlas en fila? Usa un árbol: en la raíz aún no has elegido; cada nivel fija la siguiente moneda.

1. Nivel 1: 3 elecciones (cualquiera de las tres monedas puede ir primero). Glosa: son objetos distintos, no solo valores; «primero el 1 €» no es lo mismo que «primero el 2 €».
2. Nivel 2: quedan 2 monedas → 2 ramas bajo cada vértice del nivel 1. Glosa: sin repetición: al usar una moneda, esa rama ya no la ofrece otra vez.
3. Nivel 3: queda 1 moneda → 1 hoja por camino. Total de caminos: 3 · 2 = 6
   6 · 1 = 6. Glosa: es P(3,3) = 3!
   3! = 6, el número de permutaciones de tres elementos distintos.
4. Lista de comprobación: 125, 152, 215, 251, 512, 521 (abreviado por valor). Son exactamente 6. Glosa: si contaras combinaciones C(3,3)=1 estarías ignorando el orden; aquí el orden de la fila importa.

Ejemplo 2 — PIN

Un cajero pide un PIN de 4 dígitos. El primero no puede ser 0; en el resto sí. Se permiten repeticiones. ¿Cuántos PIN distintos hay? Dibújalo como un árbol de cuatro niveles.

1. Nivel 1 (primer dígito): opciones 1–9 → 9 ramas. Glosa: el 0 queda fuera solo en la primera posición; si el árbol empezara en 0–9 tendrías 10 y estarías contando PIN ilegales.
2. Niveles 2, 3 y 4: cada uno admite 0–9 → 10 ramas por vértice. Glosa: las repeticiones están permitidas, así que el número de hijos no baja al usar un dígito: cada nivel vuelve a tener 10.
3. Regla del producto sobre el árbol: 9 · 10 = 90
   90 · 10 = 900
   900 · 10 = 9000. Glosa: cada camino raíz→hoja es un PIN. Multiplicas porque eliges «y luego» en cada nivel, no alternativas excluyentes.
4. Comprobación rápida: sin la restricción del primer dígito serían 10⁴=10000; al quitar los que empiezan por 0 quedan 10000−1000=9000. Coincide. Glosa: restar los ilegales es otra lectura del mismo árbol: 1 · 10 = 10
   10 · 10 = 100
   100 · 10 = 1000 ramas prohibidas.

Ejemplo 3 — comité vs podio

De 5 personas hay que (a) elegir un comité de 3 sin cargos y (b) elegir presidente, secretario y vocal (orden). Compara ambos números con el mismo árbol mental.

1. Podio (con orden): 5 · 4 = 20
   20 · 3 = 60. Glosa: variaciones V(5,3): el árbol tiene 5 ramas, luego 4, luego 3; cada camino es una terna ordenada de cargos.
2. Comité (sin orden): las 3! = 6 permutaciones de las mismas tres personas son el mismo comité. Glosa: en el árbol del podio, esas 6 hojas corresponden a un único conjunto {A,B,C}.
3. Por tanto C(5,3) = 60 / 6 = 10. Glosa: fórmula C(n,k)=V(n,k)/k!. Divides porque el orden sobra cuando solo importa el conjunto.
4. Comprueba: C(5,3) = 5!/(3!2!)
   5!/(3!2!) = 10. Coincide. Error típico: dejar el 60 como respuesta del comité. Glosa: si el enunciado no nombra cargos ni ranking, no uses el producto crudo del árbol ordenado.

Ejercicios

Comprueba

Tres preguntas. Responde mentalmente antes de abrir el porqué.