Soluciones Enteras No Negativas

Teoría

El problema de encontrar soluciones enteras no negativas es un concepto fundamental en el conteo combinatorio, que muchas veces se conoce como el método de "Separadores y Estrellas" (o Stars and Bars). Específicamente, te pide el número de formas de cumplir con la ecuación lineal $x_1 + x_2 + \dots + x_k = n$, donde $n$ es un entero no negativo y cada $x_i$ es un entero tal que $x_i \ge 0$. Esto equivale a repartir $n$ objetos indistinguibles (como monedas idénticas) en $k$ recipientes distinguibles (como frascos etiquetados), donde algunos recipientes pueden quedarse vacíos.

Esta técnica es esencial en las matemáticas de competencia porque muchos problemas de conteo complejos se pueden modelar como ecuaciones lineales con restricciones. Por ejemplo, encontrar los coeficientes de polinomios, repartir recursos o contar sucesiones no decrecientes de enteros a menudo se puede reducir a esta forma estándar. El poder de este método está en su capacidad de transformar un problema que parece algebraico en un arreglo geométrico de símbolos.

La intuición clave se basa en una biyección entre las soluciones de la ecuación y un arreglo específico de símbolos. Si te imaginas las $n$ unidades como "estrellas" y las divisiones entre las $k$ variables como "barras" (o separadores), una solución es simplemente una permutación lineal de estos símbolos. Como se permite que $x