Identidad de Pascal

Teoría

La Identidad de Pascal es la relación de recurrencia fundamental que define la estructura del Triángulo de Pascal. Dice que cualquier coeficiente binomial es la suma de los dos coeficientes que están justo arriba de él en el triángulo. Aunque a veces la veas como una simple regla aritmética para armar las filas del triángulo, su verdadera importancia en combinatoria viene de su lógica. Representa el principio de análisis por casos: dividir un problema de selección complejo en subcasos que no se traslapan, basándose en si incluyes o excluyes un elemento específico.

En las matemáticas de olimpiada, esta identidad es clave para simplificar sumas complejas con coeficientes binomiales y para demostrar propiedades por inducción. Sirve como base para técnicas más avanzadas, como la Hockey Stick Identity y la Vandermonde's Identity. Cuando resuelves problemas de conteo, darte cuenta de que puedes dividir un proceso de selección en "casos donde el elemento $X$ se elige" y "casos donde el elemento $X$ no se elige" es una herramienta muy poderosa que te lleva directo a esta identidad algebraica.

Fórmulas Clave

La forma estándar de la Identidad de Pascal relaciona un coeficiente binomial con índices $n$ y $k$ con coeficientes con índice $n-1$:

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

Restricciones y Condiciones:

• Esto funciona para enteros donde $1 \le k \le n-1$.
• Las condiciones de frontera (las orillas del Triángulo de Pascal) las definimos como: $$ \binom{n}{0} = \binom{n}{n} = 1 $$

Notación Alternativa: Si usas la notación $C(n,k)$ para combinaciones: $$ C(n,k) = C(n-1, k-1) + C(n-1, k) $$

Demostración

Aquí tienes una demostración combinatoria (también conocida como argumento de conteo). Este enfoque suele ser más útil que andar manipulando factoriales algebraicamente, porque resalta la lógica de teoría de conjuntos que usas en los problemas de olimpiada.

Objetivo: Mostrar que el número de formas de elegir un subconjunto de tamaño $k$ de un conjunto de tamaño $n$ es igual a la suma de las formas de elegir subconjuntos de tamaño $k-1$ y $k$ de un conjunto de tamaño $n-1$.

Paso 1: Define el problema Imagina que $S$ es un conjunto con $n$ elementos distintos. Escribe los elementos como $S = {1, 2, 3, \dots, n}$. El número total de formas de elegir un subconjunto de $k$ elementos de $S$ es, por definición, $\binom{n}{k}$.

Paso 2: Distingue un elemento específico Elige un elemento específico de $S$ al azar. Llama a este elemento "especial" $x$ (por ejemplo, que sea $x = n$). Cualquier subconjunto de tamaño $k$ que elijas de $S$ tiene que cumplir exactamente una de estas dos condiciones:

1. El subconjunto contiene a $x$.
2. El subconjunto no contiene a $x$.

Paso 3: Analiza el Caso 1 (El subconjunto contiene a $x$) Si decides que el elemento especial $x$ debe estar en tu subconjunto, ya tienes elegido 1 elemento. Para completar el subconjunto de tamaño $k$, necesitas elegir $k-1$ elementos adicionales. Estos elementos adicionales los tienes que escoger de los $n-1$ elementos que quedan en $S$ (porque ya usaste a $x$). El número de formas de hacer esto es: $$ \binom{n-1}{k-1} $$

Paso 4: Analiza el Caso 2 (El subconjunto no contiene a $x$) Si decides que el elemento especial $x$ no debe estar en tu subconjunto, entonces los $k$ elementos del subconjunto tienen que salir de los otros elementos. Tienes que elegir los $k$ elementos de los $n-1$ que sobran en $S$. El número de formas de hacer esto es: $$ \binom{n-1}{k} $$

Paso 5: Conclusión Como estos dos casos son ajenos (un subconjunto no puede contener y no contener a $x$ al mismo tiempo) y cubren todas las posibilidades, el total de formas de elegir $k$ elementos de $n$ es la suma de los conteos del Caso 1 y del Caso 2.

Así que: $$ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} $$

$\square$