Combinaciones y el triángulo de Pascal

¿Importa el orden?

En una carrera de 10 atletas, ¿cuántos podios distintos existen (oro, plata, bronce)? El orden importa: Arias-oro, Bernal-plata, Cruz-bronce es distinto a Bernal-oro, Arias-plata, Cruz-bronce. Eso son permutaciones.

Ahora imagina que solo te preguntan cuántos grupos de 3 atletas pueden formar el podio, sin importar quién gana cada medalla. Aquí el orden no importa: el grupo $\{$Arias, Bernal, Cruz$\}$ es uno solo, sin importar cómo lo ordenes internamente. Eso son combinaciones.

La diferencia es sutil pero decisiva: en combinaciones, no hay orden; solo membresía. Esta distinción resuelve el error más frecuente de los estudiantes que comienzan combinatoria.

La fórmula de las combinaciones

El número de maneras de elegir $k$ elementos de un conjunto de $n$ (sin importar el orden, sin repetición) se llama número combinatorio o coeficiente binomial y se denota $\binom{n}{k}$ (leído "n sobre k" o "n elige k").

Derivación: primero contamos arreglos ordenados de $k$ elementos elegidos de $n$: hay $n(n-1)\cdots(n-k+1) = \frac{n!}{(n-k)!}$ (permutaciones de $n$ tomados de a $k$). Pero cada grupo de $k$ elementos aparece $k!$ veces (una por cada reordenamiento interno). Dividiendo:

$$\binom{n}{k} = \frac{n!}{k!\,(n-k)!}$$

Ejemplos: $\binom{10}{3} = \frac{10!}{3! \cdot 7!} = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120$. El número de grupos de 3 atletas en el podio es 120.

Simetría y casos extremos

La fórmula revela una simetría preciosa: elegir qué $k$ elementos incluir es lo mismo que elegir qué $n-k$ elementos excluir. Por eso:

$$\binom{n}{k} = \binom{n}{n-k}$$

Esto permite simplificar cálculos: $\binom{20}{17} = \binom{20}{3} = \frac{20 \times 19 \times 18}{6} = 1140$. Siempre convierte el índice mayor al menor.

Casos extremos: $\binom{n}{0} = 1$ (hay exactamente una forma de elegir cero elementos: el conjunto vacío) y $\binom{n}{n} = 1$ (hay exactamente una forma de elegir todos: el conjunto completo). $\binom{n}{1} = n$ y $\binom{n}{n-1} = n$ por la simetría.

La identidad de Pascal y el triángulo

La identidad de Pascal es la relación de recurrencia que permite construir $\binom{n}{k}$ a partir de valores anteriores:

$$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$$

Prueba combinatoria (sin cuentas): queremos elegir $k$ elementos de $\{1, 2, \ldots, n\}$. Miramos si el elemento $n$ está en la selección o no. Si sí está: elegimos los $k-1$ restantes de los otros $n-1$ elementos: $\binom{n-1}{k-1}$ formas. Si no está: elegimos los $k$ elementos de los otros $n-1$: $\binom{n-1}{k}$ formas. Los casos son disjuntos y cubren todo: sumamos.

El triángulo de Pascal se construye poniendo $\binom{n}{k}$ en la fila $n$, columna $k$. Cada celda es la suma de los dos que tiene encima. Memorizar las primeras filas (hasta $n=6$) acelera enormemente los cálculos en competencia.

Caminos en una cuadrícula

Problema clásico de olimpiada: ¿Cuántos caminos hay de la esquina inferior-izquierda a la esquina superior-derecha de una cuadrícula de $m \times n$, si solo se puede moverse hacia la derecha (D) o hacia arriba (A)?

Un camino completo consiste exactamente en $m$ movimientos hacia la derecha y $n$ movimientos hacia arriba, en algún orden — un total de $m+n$ movimientos. El número de caminos es el número de formas de elegir en cuáles de los $m+n$ pasos se avanza a la derecha:

$$\binom{m+n}{m} = \binom{m+n}{n} = \frac{(m+n)!}{m! \cdot n!}$$

Ejemplo: en una cuadrícula $4 \times 3$ hay $\binom{7}{4} = \binom{7}{3} = 35$ caminos. Nota que esta fórmula es exactamente la de multiconjuntos con $n_D = m$ y $n_A = n$: los caminos son anagramas de la cadena $\underbrace{DD\cdots D}_{m}\underbrace{AA\cdots A}_{n}$.

La identidad de Vandermonde

La identidad de Vandermonde es una generalización poderosa:

$$\binom{m+n}{r} = \sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k}$$

Prueba combinatoria: queremos elegir $r$ personas de un grupo con $m$ hombres y $n$ mujeres. Si elegimos $k$ hombres (de $m$) y $r-k$ mujeres (de $n$), hay $\binom{m}{k}\binom{n}{r-k}$ formas. Sumando sobre todos los $k$ posibles (de 0 a $r$) cubrimos todos los casos disjuntos.

Caso especial útil (Vandermonde con $m=n=r$): $\binom{2n}{n} = \sum_{k=0}^{n}\binom{n}{k}^2$. Esto dice que el coeficiente central del triángulo de Pascal es la suma de los cuadrados de una fila. Aparece en problemas olímpicos de nivel 2.