24. Identidades combinatorias

24.1 Introducción

Una identidad combinatoria es una igualdad entre expresiones que representan la misma cantidad. La demostración no depende solamente de transformar símbolos: también puede consistir en contar un conjunto de objetos desde dos puntos de vista.

Este enfoque se conoce como doble conteo. Si el lado izquierdo y el lado derecho cuentan el mismo conjunto de resultados, deben ser iguales.

24.2 Identidad de simetría

La identidad más básica es:

El lado izquierdo elige los k elementos que forman parte del grupo. El lado derecho elige los n-k elementos que quedan fuera. Ambas decisiones describen exactamente el mismo subconjunto.

24.3 Identidad de Pascal

Para demostrarla, fijamos un elemento especial. Una selección de k elementos:

• Incluye el elemento especial: elegimos k-1 de los n-1 restantes.
• No incluye el elemento especial: elegimos k de los n-1 restantes.

Los dos casos son excluyentes y cubren todas las selecciones.

24.4 Simulación de identidades

Elige una identidad y sus parámetros para comparar numéricamente ambos lados.

24.5 Identidad de la suma de una fila

La suma de todos los coeficientes de una fila es:

El lado izquierdo agrupa los subconjuntos según su tamaño. El lado derecho cuenta cada elemento con dos opciones: estar dentro o fuera del subconjunto.

24.6 Identidad de suma acumulada

Una suma de coeficientes en diagonal cumple:

Esta identidad se observa en las diagonales del triángulo de Pascal y permite reemplazar una suma de varios términos por un único coeficiente.

24.7 Identidad de Vandermonde

Una identidad importante para combinar dos grupos es:

Para formar un grupo de r elementos a partir de dos conjuntos, podemos elegir k del primer conjunto y r-k del segundo. Sumamos todas las posibilidades para k.

24.8 Un ejemplo de doble conteo

Supongamos que tenemos 5 elementos y queremos elegir 2. Podemos contarlos directamente con C(5,2), o clasificarlos según incluya o no un elemento especial:

Ambos métodos cuentan las mismas 10 selecciones.

24.9 Un ejemplo en JavaScript

Podemos verificar la identidad de Pascal calculando sus dos lados.

function binomial(n, k) {
  if (k < 0 || k > n) return 0;
  k = Math.min(k, n - k);
  let valor = 1;
  for (let indice = 1; indice <= k; indice += 1) {
    valor = valor * (n - indice + 1) / indice;
  }
  return valor;
}

const n = 8;
const k = 3;
const izquierda = binomial(n, k);
const derecha = binomial(n - 1, k - 1) + binomial(n - 1, k);

console.log(izquierda === derecha);

24.10 Identidades y algoritmos

Una identidad puede convertirse en un algoritmo alternativo. Por ejemplo, la simetría permite reemplazar k por n-k y elegir el menor de los dos valores.

function indicePequeño(n, k) {
  return Math.min(k, n - k);
}

console.log(indicePequeño(100, 97)); // Conviene calcular con 3
console.log(indicePequeño(100, 3));  // Ya es pequeño

El resultado matemático no cambia, pero el cálculo puede requerir menos operaciones.

24.11 Cómo construir una demostración combinatoria

1. Identificar el conjunto que se desea contar.
2. Interpretar el lado izquierdo como una forma de contar sus elementos.
3. Interpretar el lado derecho mediante una clasificación o elección alternativa.
4. Comprobar que ambos métodos incluyen todos los casos y ninguno se repite.
5. Concluir que las expresiones son iguales porque cuentan el mismo conjunto.

24.12 Aplicaciones en informática

• Demostrar fórmulas utilizadas por algoritmos.
• Encontrar cálculos equivalentes más eficientes.
• Verificar resultados mediante dos métodos independientes.
• Contar configuraciones clasificándolas por una propiedad.
• Analizar subconjuntos, rutas y asignaciones.
• Diseñar pruebas de consistencia para funciones de conteo.

24.13 Errores frecuentes

• Comparar expresiones sin demostrar que cuentan el mismo conjunto.
• Usar casos que se superponen en una suma.
• Omitir una posibilidad en una clasificación.
• Aplicar una identidad fuera de sus condiciones válidas.
• Confundir una igualdad numérica accidental con una identidad general.

24.14 Qué debes recordar de este tema

• Una identidad combinatoria expresa dos formas de contar lo mismo.
• El doble conteo es una herramienta para demostrar igualdades.
• La simetría y la identidad de Pascal son ejemplos fundamentales.
• Las sumas de filas y diagonales producen nuevos coeficientes.
• Las identidades pueden mejorar algoritmos y verificaciones.
• Una demostración debe cubrir todos los casos sin duplicarlos.

24.15 Conclusión

Las identidades combinatorias muestran que un mismo conjunto puede contarse mediante estrategias diferentes. Esta forma de razonar permite demostrar fórmulas, descubrir relaciones y diseñar cálculos más eficientes.

En el próximo tema estudiaremos el principio del palomar, una herramienta para demostrar que ciertas coincidencias son inevitables.