El triángulo de Pascal y sus identidades profundas

El triángulo que esconde todo

En el siglo XVII, Blaise Pascal publicó su "Traité du triangle arithmétique", un texto de apenas 66 páginas que sintetizaba décadas de correspondencia con Fermat sobre probabilidad y conteo. El triángulo que lleva su nombre era conocido mucho antes: los matemáticos indios lo estudiaban desde el siglo II a.C. (donde se llamaba "meru prastara"), Omar Khayyam lo usaba en el siglo XI, y Yang Hui lo popularizó en China en el siglo XIII. Sin embargo, el tratado de Pascal fue el primero en explotar sistemáticamente las identidades del triángulo como herramienta combinatoria.

El triángulo de Pascal se construye así: escribimos $1$ en la cima (fila 0). Cada entrada siguiente es la suma de las dos entradas directamente encima. La entrada en la fila $n$ y posición $k$ (contando desde 0) resulta ser exactamente $\binom{n}{k}$, el coeficiente binomial que cuenta el número de subconjuntos de $k$ elementos de un conjunto de $n$ elementos.

Esta identificación no es trivial: la verifica la regla de Pascal, que es simultáneamente la fórmula de construcción del triángulo y la relación de recurrencia de los coeficientes binomiales. Todo el capítulo que sigue fluye de esta identificación.

En las olimpiadas iberoamericanas, el triángulo de Pascal aparece en problemas de conteo con restricciones, en demostraciones de divisibilidad de coeficientes binomiales, y como substrato de identidades que se usan en problemas de doble conteo. Comprender el triángulo en profundidad es prerequisito para el resto del capítulo.

La regla de Pascal y su demostración combinatoria

La regla de Pascal afirma que para $1 \leq k \leq n-1$:

La demostración algebraica es directa: $\binom{n-1}{k-1} + \binom{n-1}{k} = \frac{(n-1)!}{(k-1)!(n-k)!} + \frac{(n-1)!}{k!(n-1-k)!} = \frac{(n-1)! \cdot k}{k!(n-k)!} + \frac{(n-1)!(n-k)}{k!(n-k)!} = \frac{(n-1)!(k + n - k)}{k!(n-k)!} = \frac{n!}{k!(n-k)!} = \binom{n}{k}$.

La demostración combinatoria es más iluminadora: $\binom{n}{k}$ cuenta los subconjuntos de tamaño $k$ de $\{1, 2, \ldots, n\}$. Fijamos el elemento $n$ y separamos según si $n$ está en el subconjunto o no. Los subconjuntos de tamaño $k$ que contienen al elemento $n$ corresponden biunívocamente a subconjuntos de tamaño $k-1$ del conjunto $\{1, \ldots, n-1\}$: hay $\binom{n-1}{k-1}$ de ellos. Los subconjuntos de tamaño $k$ que no contienen al elemento $n$ son subconjuntos de tamaño $k$ del conjunto $\{1, \ldots, n-1\}$: hay $\binom{n-1}{k}$ de ellos. Como estas dos clases son disjuntas y su unión da todos los subconjuntos de tamaño $k$, obtenemos la regla de Pascal.

Esta demostración combinatoria ilustra el método del elemento distinguido: fijar un elemento y separar según si pertenece o no al subconjunto. Es una técnica que reaparece constantemente en olimpiadas.

Los casos límite son $\binom{n}{0} = 1$ (hay exactamente un subconjunto vacío) y $\binom{n}{n} = 1$ (hay exactamente un subconjunto de tamaño $n$, el total). Junto con la regla de Pascal, estos valores de borde determinan completamente el triángulo.

Identidades fundamentales del triángulo

Identidad de la suma de filas: La suma de todos los coeficientes de la fila $n$ es $2^n$:

Demostración: en el Teorema del Binomio (próxima lección), ponemos $x = y = 1$: $(1+1)^n = \sum_{k=0}^{n} \binom{n}{k} 1^k 1^{n-k} = \sum_{k=0}^{n} \binom{n}{k}$.

Demostración combinatoria: $\sum_{k=0}^{n} \binom{n}{k}$ cuenta todos los subconjuntos de $\{1, \ldots, n\}$, que son $2^n$ (cada elemento puede estar o no estar).

Identidad de la suma alternada: $\sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0$ para $n \geq 1$. Demostración: Teorema del Binomio con $x = -1$, $y = 1$: $(1-1)^n = 0 = \sum_{k=0}^{n} \binom{n}{k} (-1)^k$. Equivalentemente: el número de subconjuntos de tamaño par de $\{1, \ldots, n\}$ es igual al número de subconjuntos de tamaño impar.

Simetría: $\binom{n}{k} = \binom{n}{n-k}$. Demostración: un subconjunto de tamaño $k$ se corresponde biunívocamente con su complemento de tamaño $n-k$.

Identidad de absorción: $\binom{n}{k} = \frac{n}{k} \binom{n-1}{k-1}$ para $k \geq 1$. Demostración algebraica inmediata. Útil para simplificar expresiones con factoriales.

Identidad del pasillo (Hockey Stick): Para $n \geq r \geq 0$: $\sum_{i=r}^{n} \binom{i}{r} = \binom{n+1}{r+1}$. Demostración por inducción en $n$: el caso base $n = r$ da $\binom{r}{r} = 1 = \binom{r+1}{r+1}$ ✓. Para el paso inductivo: $\sum_{i=r}^{n+1} \binom{i}{r} = \binom{n+1}{r+1} + \binom{n+1}{r} = \binom{n+2}{r+1}$ usando la regla de Pascal. El nombre "hockey stick" viene de la forma que dibuja la identidad en el triángulo: una diagonal y su diagonal oblicua forman la figura de un palo de hockey.

Demostración combinatoria del Hockey Stick: $\binom{n+1}{r+1}$ cuenta subconjuntos de tamaño $r+1$ de $\{1, \ldots, n+1\}$. Particionamos según el mayor elemento del subconjunto: si el mayor es $i+1$ (con $r \leq i \leq n$), hay $\binom{i}{r}$ formas de elegir los $r$ elementos restantes de $\{1, \ldots, i\}$. Sumando sobre todos los posibles mayores elementos se obtiene $\sum_{i=r}^{n} \binom{i}{r}$.

La identidad de Vandermonde

La identidad de Vandermonde es una de las identidades más poderosas de la combinatoria:

Enunciado: Para enteros no negativos $m$, $n$, $r$ con $r \leq m + n$:

Demostración combinatoria: $\binom{m+n}{r}$ cuenta los subconjuntos de tamaño $r$ de un conjunto $A \cup B$ con $|A| = m$, $|B| = n$, $A \cap B = \emptyset$. Fijamos cuántos elementos del subconjunto vienen de $A$: si vienen $k$ elementos de $A$ (y por tanto $r - k$ de $B$), hay $\binom{m}{k} \binom{n}{r-k}$ formas. Sumando sobre todos los $k$ posibles (de $\max(0, r-n)$ a $\min(m, r)$): $\binom{m+n}{r} = \sum_{k=0}^{r} \binom{m}{k} \binom{n}{r-k}$ (con la convención $\binom{a}{b} = 0$ si $b < 0$ o $b > a$).

Caso especial importante: $m = n = r$: $\binom{2n}{n} = \sum_{k=0}^{n} \binom{n}{k}^2$. Este es el número de subconjuntos de tamaño $n$ de un conjunto de $2n$ elementos, y también la suma de cuadrados de los coeficientes de la fila $n$.

Aplicación en olimpiadas: La identidad de Vandermonde frecuentemente aparece disfrazada. Si se pide demostrar $\sum_{k=0}^{r} \binom{m}{k} \binom{n}{r-k} = \binom{m+n}{r}$, la demostración combinatoria (bipartición de un conjunto de $m+n$ elementos) es más elegante y más corta que la algebraica.

Generalización (Chu–Vandermonde): $\sum_{k=0}^{r} \binom{m}{k} \binom{n}{r-k} = \binom{m+n}{r}$ se extiende a valores no enteros de $m$ y $n$ usando la función Gamma, pero para olimpiadas basta el caso entero.

Divisibilidad en el triángulo: primos y el teorema de Kummer

Una de las propiedades más bellas del triángulo de Pascal desde el punto de vista de la teoría de números es el patrón de divisibilidad de sus entradas.

Teorema: Si $p$ es primo, entonces $p \mid \binom{p}{k}$ para $1 \leq k \leq p-1$. Demostración: $\binom{p}{k} = \frac{p!}{k!(p-k)!}$. El numerador $p!$ tiene exactamente un factor $p$ (el propio $p$). El denominador $k!(p-k)!$ con $1 \leq k \leq p-1$ no tiene factor $p$ (pues $k < p$ y $p-k < p$, y $p$ es primo). Por tanto $p \mid \binom{p}{k}$.

Corolario (Pequeño Teorema de Fermat por inducción): $(a+b)^p \equiv a^p + b^p \pmod{p}$ para todo primo $p$. Pues $(a+b)^p = \sum_{k=0}^{p} \binom{p}{k} a^k b^{p-k}$ y los términos intermedios ($1 \leq k \leq p-1$) son divisibles por $p$.

Triángulo de Sierpiński: Si coloreamos las entradas del triángulo de Pascal según si son pares (blanco) o impares (negro), obtenemos el fractal de Sierpiński. Esto se debe al Teorema de Lucas: para primo $p$, $\binom{m}{n} \equiv \prod_{i} \binom{m_i}{n_i} \pmod{p}$, donde $m = \sum_i m_i p^i$ y $n = \sum_i n_i p^i$ son las representaciones en base $p$. En particular, $\binom{m}{n}$ es par (divisible por 2) si y solo si algún dígito en base 2 de $n$ excede al correspondiente de $m$.

Problema paradigmático (Iberoamericana 1995): Demostrar que $\binom{2p}{p} \equiv 2 \pmod{p^2}$ para todo primo impar $p$. Solución: $\binom{2p}{p} = \frac{(2p)!}{(p!)^2} = \frac{(2p)(2p-1)\cdots(p+1)}{p!} = \frac{\prod_{j=1}^{p}(p+j)}{p!}$. El numerador es $\prod_{j=1}^{p}(p+j) = p^p \prod_{j=1}^{p}(1 + p/j)$ ... más directamente: $\binom{2p}{p} = 2 \cdot \frac{(2p-1)(2p-3)\cdots 3 \cdot 1}{(p-1)!} \cdot \frac{1}{1}$. Usando que $(2p-k)(k) = 2pk - k^2 \equiv -k^2 \pmod{p}$, el producto telescópico da $\binom{2p}{p} = 2 + p^2 \cdot M$ para algún entero $M$, luego $\binom{2p}{p} \equiv 2 \pmod{p^2}$.

Estrategia olímpica: elegir la identidad correcta

En olimpiadas, los problemas que involucran coeficientes binomiales generalmente requieren identificar cuál identidad del triángulo de Pascal es la clave. La siguiente guía cubre los patrones más frecuentes.

Sumas de una sola fila: Si aparece $\sum_k \binom{n}{k}$, usar suma de fila = $2^n$. Si la suma tiene signos alternos $\sum_k (-1)^k \binom{n}{k}$, la respuesta es 0 para $n \geq 1$.

Sumas con pesos lineales: $\sum_{k=0}^{n} k \binom{n}{k} = n \cdot 2^{n-1}$. Demostración: $k \binom{n}{k} = n \binom{n-1}{k-1}$ (identidad de absorción), luego la suma es $n \sum_{k=1}^{n} \binom{n-1}{k-1} = n \cdot 2^{n-1}$.

Sumas diagonales: Si la suma recorre una diagonal del triángulo, usar el Hockey Stick.

Sumas de productos de dos filas: Si la suma es $\sum_k \binom{m}{k}\binom{n}{r-k}$, usar Vandermonde.

Congruencias: Si se pide $\binom{n}{k} \pmod{p}$, usar el Teorema de Lucas para reducir a dígitos en base $p$.

Ejemplo de síntesis (Cono Sur 2009, P2): Calcular $\sum_{k=0}^{n} \binom{n}{k}^2$. Por Vandermonde con $m = n$ y $r = n$: $\sum_{k=0}^{n} \binom{n}{k} \binom{n}{n-k} = \binom{2n}{n}$. Usando la simetría $\binom{n}{n-k} = \binom{n}{k}$, la suma se reescribe como $\sum_{k=0}^{n} \binom{n}{k}^2 = \binom{2n}{n}$.