Combinatoria - 19. Coeficientes binomiales

19.1 Introducción

En el tema 16 estudiamos las combinaciones sin repetición. El número de combinaciones de n elementos tomados de k en k puede escribirse de una forma compacta como C(n, k) o como un coeficiente binomial.

Estos números conectan el conteo de subconjuntos con el álgebra, el triángulo de Pascal, el teorema del binomio y numerosos algoritmos.

19.2 Notación

El coeficiente binomial se representa de varias maneras:

C(n, k) = (n sobre k) = n choose k

Se lee “n sobre k” y significa la cantidad de formas de elegir k elementos de un conjunto de n elementos sin importar el orden.

19.3 Fórmula factorial

Para enteros con 0 ≤ k ≤ n:

C(n, k) = n! / (k! × (n - k)!)

El factorial n! cuenta ordenamientos, pero se divide por k! y por (n-k)! para eliminar los ordenamientos equivalentes de los elementos elegidos y no elegidos.

19.4 Ejemplo de cálculo

El número de formas de elegir 2 elementos de un conjunto de 5 es:

C(5, 2) = 5! / (2! × 3!)
C(5, 2) = 120 / 12 = 10

Las 10 selecciones son subconjuntos diferentes; el orden de sus elementos no genera nuevos casos.

19.5 Simulación: calcular y construir una fila

Indica n y k para calcular C(n,k). La fila completa muestra todos los coeficientes C(n,0), C(n,1), ..., C(n,n).

19.6 Propiedad de simetría

Los coeficientes binomiales cumplen:

C(n, k) = C(n, n - k)

Elegir k elementos equivale a decidir cuáles n-k elementos quedan fuera. Por ejemplo:

C(8, 3) = C(8, 5)

Esta propiedad permite reemplazar un cálculo por otro con un valor menor de k.

19.7 Identidad de Pascal

Una relación fundamental es:

C(n, k) = C(n - 1, k - 1) + C(n - 1, k)

Una selección de k elementos de n puede clasificarse según incluya o no un elemento particular. En el primer caso se eligen k-1 de los n-1 restantes; en el segundo se eligen k de ellos.

19.8 Un ejemplo en JavaScript

Podemos calcular un coeficiente binomial usando la identidad de Pascal y casos base.

function binomial(n, k) {
  if (k === 0 || k === n) return 1;
  return binomial(n - 1, k - 1) + binomial(n - 1, k);
}

console.log(binomial(5, 2));
console.log(binomial(6, 3));

Para valores grandes, la versión recursiva directa repite cálculos. Más adelante veremos técnicas para guardar resultados y mejorar la eficiencia.

19.9 Cálculo iterativo

Una forma de construir una fila completa es comenzar con 1 y usar la relación entre términos consecutivos:

function filaBinomial(n) {
  const fila = [1];
  for (let k = 1; k <= n; k += 1) {
    const anterior = fila[k - 1];
    fila.push(anterior * (n - k + 1) / k);
  }
  return fila;
}

console.log(filaBinomial(5));

La fila resultante para n = 5 es 1, 5, 10, 10, 5, 1.

19.10 Interpretación combinatoria

Cada coeficiente binomial representa una cantidad de selecciones:

C(4, 0) = 1 selección vacía
C(4, 1) = 4 selecciones de un elemento
C(4, 2) = 6 selecciones de dos elementos
C(4, 3) = 4 selecciones de tres elementos
C(4, 4) = 1 selección de todos los elementos

La suma de una fila cuenta todos los subconjuntos posibles de un conjunto de n elementos.

19.11 Suma de los coeficientes

Para cualquier n:

C(n, 0) + C(n, 1) + ... + C(n, n) = 2ⁿ

El lado izquierdo cuenta subconjuntos agrupados por tamaño. El lado derecho cuenta cada elemento con dos posibilidades: pertenecer o no pertenecer al subconjunto.

19.12 Relación con el triángulo de Pascal

El triángulo de Pascal organiza los coeficientes binomiales por filas. La fila n contiene:

C(n, 0), C(n, 1), C(n, 2), ..., C(n, n)

Los bordes siempre valen 1 y cada valor interior es la suma de los dos valores que están encima. El próximo tema estudiará este triángulo con más detalle.

19.13 Aplicaciones en informática

Contar subconjuntos y selecciones.
Calcular posibilidades en problemas de probabilidad.
Construir filas del triángulo de Pascal.
Desarrollar potencias de binomios.
Analizar algoritmos de programación dinámica.
Contar configuraciones en pruebas y búsquedas.

19.14 Errores frecuentes

Confundir C(n,k) con una variación.
Olvidar dividir por k!.
Usar valores donde k es mayor que n.
Confundir C(n,k) con n^k.
Calcular factoriales enormes sin simplificar.

19.15 Qué debes recordar de este tema

C(n,k) cuenta selecciones de k elementos entre n sin importar el orden.
Su fórmula es n! / (k!(n-k)!).
Se cumple C(n,k) = C(n,n-k).
La identidad de Pascal relaciona coeficientes de filas consecutivas.
La suma de una fila es 2ⁿ.
Los coeficientes binomiales aparecen en conteo, álgebra y algoritmos.

19.16 Conclusión

Los coeficientes binomiales proporcionan una notación compacta para las combinaciones y una estructura rica de propiedades. Pueden calcularse mediante factoriales, recurrencias o filas del triángulo de Pascal.

En el próximo tema estudiaremos el triángulo de Pascal y sus patrones combinatorios.

Volver al índice

19. Coeficientes binomiales