Usa funciones generatrices para particiones.
Las funciones generatrices de particiones son una herramienta poderosa en combinatoria que te sirven para estudiar $p(n)$, que es el número de formas de escribir un entero $n$ como una suma de enteros positivos donde no importa el orden de los sumandos. A diferencia de las permutaciones o combinaciones estándar, las particiones suelen ser difíciles de contar usando factoriales simples en forma cerrada. Las funciones generatrices transforman el problema de contar particiones en la manipulación algebraica de polinomios infinitos (series de potencias). Al codificar la elección de las partes en los exponentes de una variable $x$, puedes usar la estructura de las series geométricas para resolver problemas de conteo complejos.
La idea fundamental es que puedes describir una partición contando cuántas veces aparece cada entero en la suma. Por ejemplo, la partición $5 = 2 + 1 + 1 + 1$ consiste en tres $1$s y un $2$. En el contexto de las funciones generatrices, representas la elección de cuántas veces aparece el entero $k$ en una partición como un factor polinomial o de serie $(1 + x^k + x^{2k} + x^{3k} + \dots)$. Cuando multiplicas estos factores para todos los enteros $k$ posibles, el coeficiente resultante de $x^n$ cuenta exactamente el número de formas de formar la suma $n$.
Esta técnica es muy importante en las olimpiadas de matemáticas (AIME/USAMO) porque maneja las restricciones