Formas de escribir n como suma de enteros positivos.
Una partición de un entero positivo $n$ es una forma de escribir $n$ como una suma de enteros positivos. Dos sumas que solo se diferencian en el orden de sus sumandos se consideran la misma partición. Por ejemplo, las particiones de 4 son $4$, $3+1$, $2+2$, $2+1+1$ y $1+1+1+1$. Al número de particiones de $n$ lo escribimos con la función de partición $p(n)$. A diferencia de las composiciones (donde el orden sí importa), no hay una expresión cerrada simple para $p(n)$, lo que hace que el estudio de las particiones sea un campo muy rico que incluye relaciones de recurrencia, funciones generatrices y análisis asintótico.
Las particiones son una herramienta fundamental en combinatoria y teoría de números, y aparecen seguido en problemas sobre distribuir objetos indistinguibles en cajas indistinguibles. Un concepto clave para resolver problemas de particiones es el uso de los diagramas de Ferrers (o diagramas de Young), que representan las particiones gráficamente como filas de puntos o cuadrados. Esta representación visual te permite entender el concepto de particiones conjugadas, que obtienes al reflejar el diagrama sobre la diagonal principal, y esto te da demostraciones biyectivas muy elegantes para identidades que relacionan distintos tipos de particiones.
Para las olimpiadas de matemáticas, la técnica más poderosa para manejar particiones es el método de las funciones generatrices. Al transformar las restricciones de las partes de la partición (por ejemplo, partes distintas, partes impares, partes congruentes a $k \pmod m$) en restricciones algebraicas de productos infinitos, puedes resolver identidades combinatorias complejas mediante manipulación algebraica. Esto conecta los problemas de conteo discreto con las propiedades de los polinomios y las series infinitas.
1. Función Generatriz de Euler La función generatriz para $p(n)$, el número de particiones sin restricciones de $n$, está dada por el producto infinito: $$ \sum_{n=0}^{\infty} p(n)x^n = \prod_{k=1}^{\infty} \frac{1}{1-x^k} = (1+x+x^2+\dots)(1+x^2+x^4+\dots)(1+x^3+x^6+\dots)\dots $$
2. Identidad de Euler (Impares vs. Distintas) El número de particiones de $n$ en partes distintas es igual al número de particiones de $n$ en partes impares: $$ p_{\text{distinct}}(n) = p_{\text{odd}}(n) $$
3. Pentagonal Number Theorem Este teorema te da una relación de recurrencia para calcular $p(n)$ de forma eficiente. $$ \prod_{k=1}^{\infty} (1-x^k) = \sum_{k=-\infty}^{\infty} (-1)^k x^{k(3k-1)/2} = 1 - x - x^2 + x^5 + x^7 - x^{12} - x^{15} + \dots $$ Esto te lleva a la recurrencia: $$ p(n) = \sum_{k \neq 0, (-1)^{k-1} \frac{k(3k-1)}{2} \le n} (-1)^{k-1} p\left(n - \frac{k(3k-1)}{2}\right) $$
4. Particiones con restricciones de tamaño La función generatriz para las particiones de $n$ en partes de tamaño máximo $m$ (que es equivalente a particiones con máximo $m$ partes) es: $$ \sum_{n=0}^{\infty} p_m(n)x^n = \prod_{k=1}^{m} \frac{1}{1-x^k} $$
Teorema: El número de particiones de $n$ en partes distintas es igual al número de particiones de $n$ en partes impares.
Demostración mediante funciones generatrices:
Digamos que $p_d(n)$ es el número de particiones de $n$ en partes distintas y $p_o(n)$ es el número de particiones de $n$ en partes impares. Lo que hay que mostrar es que sus funciones generatrices son idénticas.
Paso 1: Construye la función generatriz para partes distintas. Para una partición en partes distintas, cada entero $k$ puede aparecer en la suma 0 o 1 vez. Por lo tanto, el factor que corresponde al entero $k$ en la función generatriz es $(1 + x^k)$. La función generatriz para particiones en partes distintas es: $$ D(x) = \sum_{n=0}^{\infty} p_d(n)x^n = \prod_{k=1}^{\infty} (1+x^k) = (1+x)(1+x^2)(1+x^3)(1+x^4)\dots $$
Paso 2: Manipulación algebraica. Usa la identidad de diferencia de cuadrados, $1+y = \frac{1-y^2}{1-y}$. Aplica esto a cada término del producto: $$ 1+x^k = \frac{1-x^{2k}}{1-x^k} $$ Al sustituir esto en la expresión para $D(x)$: $$ D(x) = \prod_{k=1}^{\infty} \frac{1-x^{2k}}{1-x^k} $$
Paso 3: Expande y cancela términos. Escribe los primeros términos del numerador y del denominador para ver cómo se van cancelando: $$ D(x) = \frac{(1-x^2)(1-x^4)(1-x^6)(1-x^8)\dots}{(1-x)(1-x^2)(1-x^3)(1-x^4)\dots} $$ Nota que cada término de la forma $(1-x^{2k})$ en el numerador aparece exactamente una vez en el denominador (ya que el denominador contiene $(1-x^m)$ para todos los enteros $m$, incluyendo todos los pares).
Puedes reescribir el denominador separando las potencias pares de las impares: $$ \text{Denominador} = \left[ \prod_{k=1}^{\infty} (1-x^{2k}) \right] \cdot \left[ \prod_{k=1}^{\infty} (1-x^{2k-1}) \right] $$
Paso 4: Simplifica. Sustituye esto de nuevo en la expresión de $D(x)$: $$ D(x) = \frac{\prod_{k=1}^{\infty} (1-x^{2k})}{\left[ \prod_{k=1}^{\infty} (1-x^{2k}) \right] \cdot \left[ \prod_{k=1}^{\infty} (1-x^{2k-1}) \right]} $$ Los productos sobre las potencias pares se cancelan por completo: $$ D(x) = \frac{1}{\prod_{k=1}^{\infty} (1-x^{2k-1})} = \prod_{k=1}^{\infty} \frac{1}{1-x^{2k-1}} $$
Paso 5: Interpreta el resultado. La expresión resultante, $\prod_{k=1}^{\infty} \frac{1}{1-x^{2k-1}}$, representa la función generatriz donde las partes disponibles son solo los enteros impares ($1, 3, 5, \dots$) y cada parte se puede repetir cualquier cantidad de veces (por la forma de la serie geométrica $\frac{1}{1-y} = 1+y+y^2+\dots$).
Esta es precisamente la función generatriz para particiones en partes impares, que llamaremos $O(x)$. $$ D(x) = O(x) $$ Como las funciones generatrices son idénticas, los coeficientes tienen que ser iguales para toda $n$. Por lo tanto, $p_d(n) = p_o(n)$. $\square$