Combinatoria y triángulo de Pascal

La idea

La combinatoria responde a la pregunta «¿de cuántas maneras?» sin tener que enumerarlas. Todo se apoya en dos reglas: el principio del producto (si una elección tiene m opciones y la siguiente n, hay m·n resultados) y el principio de la suma (alternativas disjuntas se suman). De ahí salen las permutaciones de n objetos distintos, n!, las variaciones de n tomados de k en k cuando el orden importa, n!/(n − k)!, y las combinaciones cuando el orden no importa, C(n, k) = n!/(k!(n − k)!), que se lee «n sobre k».

Los números C(n, k) se llaman coeficientes binomiales porque son los coeficientes del desarrollo de (a + b)ⁿ. Cumplen dos propiedades fundamentales: la simetría C(n, k) = C(n, n − k), porque elegir k objetos equivale a descartar n − k, y la recurrencia de Pascal C(n, k) = C(n − 1, k − 1) + C(n − 1, k), que separa los casos «el último objeto entra» y «no entra». Colocando estos números en filas se obtiene el triángulo de Pascal, donde cada casilla es la suma de las dos que tiene encima; la suma de una fila completa es 2ⁿ, el número total de subconjuntos de un conjunto de n elementos.

Cuando hay repeticiones o restricciones aparecen variantes: combinaciones con repetición C(n + k − 1, k), permutaciones de objetos repetidos n!/(n₁! n₂! ⋯), y el principio de inclusión-exclusión para contar uniones de conjuntos que se solapan. El principio del palomar cierra el repertorio con un argumento sencillísimo y potente: si hay más objetos que cajas, alguna caja contiene al menos dos objetos. Estas cuentas son la base del cálculo de probabilidades en espacios equiprobables y del análisis de algoritmos que exploran configuraciones.

Fórmulas clave

• PermutacionesP(n) = n! = n (n − 1) ⋯ 2 · 1
• Variaciones (orden sí importa)V(n, k) = n! / (n − k)!
• Combinaciones (orden no importa)C(n, k) = n! / [k! (n − k)!]
• Recurrencia de PascalC(n, k) = C(n − 1, k − 1) + C(n − 1, k)
• Binomio de Newton(a + b)ⁿ = Σ_{k=0..n} C(n, k) a^{n−k} b^k
• Suma de una filaΣ_{k=0..n} C(n, k) = 2ⁿ

Dónde se aplica

Las loterías se diseñan con combinaciones: acertar 6 números entre 49 tiene una probabilidad de 1 entre C(49, 6) = 13 983 816. En informática, el número de subconjuntos 2ⁿ mide el tamaño del espacio de búsqueda de problemas como la mochila o la selección de variables en un modelo, y explica por qué hace falta heurística en cuanto n crece. En genética se cuentan genotipos posibles con permutaciones de alelos repetidos, y en diseño de experimentos las combinaciones determinan cuántos tratamientos hay que probar y cuántas comparaciones múltiples habrá que corregir después.

Con programación (Python)

import math

def variaciones(n, k):
    return math.factorial(n) // math.factorial(n - k)

def combinaciones(n, k):
    return math.comb(n, k)

n, k = 6, 3
print(f"{n}! =", math.factorial(n))
print(f"V({n},{k}) =", variaciones(n, k))
print(f"C({n},{k}) =", combinaciones(n, k))
print("simetria: C(7,2) =", combinaciones(7, 2), "y C(7,5) =", combinaciones(7, 5))

print("Triangulo de Pascal:")
fila = [1]
for i in range(7):
    print(" " * (3 * (6 - i)), "  ".join(f"{v:3}" for v in fila))
    fila = [1] + [fila[j] + fila[j + 1] for j in range(len(fila) - 1)] + [1]

# Enumeracion real de los subconjuntos de tamano k
import itertools
subs = list(itertools.combinations(range(1, n + 1), k))
print(f"hay {len(subs)} subconjuntos de {k} elementos; los 5 primeros:", subs[:5])
print("loteria 6/49:", combinaciones(49, 6), "boletos posibles")

La versión en JavaScript, editable y ejecutable en el navegador, está en la página interactiva del tema.

Temas relacionados

Probabilidad clásica · Distribución binomial · Recursión y memoización · El problema de la mochila