Soluciones con límites superiores o inferiores.
Las soluciones con variables acotadas se refieren al problema de encontrar el número de soluciones enteras de una ecuación lineal de la forma $x_1 + x_2 + \dots + x_k = n$, sujeta a restricciones específicas en las variables $x_i$. Mientras que el método estándar de "Separadores" (Stars and Bars) cuenta soluciones donde las variables son enteros no negativos ($x_i \ge 0$) o enteros positivos ($x_i \ge 1$), los problemas de variables acotadas introducen límites inferiores arbitrarios ($x_i \ge a_i$) o límites superiores ($x_i \le b_i$). Estos problemas aparecen seguido en competencias como el AMC 12 y el AIME, modelando situaciones como distribuir objetos idénticos en recipientes distintos con requisitos mínimos o límites de capacidad.
Manejar límites inferiores es una extensión directa de la técnica estándar. Si aplicas un cambio de variable (un desplazamiento), puedes transformar un problema con límites inferiores en un problema estándar de enteros no negativos. Por ejemplo, si $x_i \ge 5$, puedes definir una nueva variable $y_i = x_i - 5 \ge 0$, lo que básicamente "pre-distribuye" la cantidad necesaria y te permite resolver para el resto. Esta transformación conserva la correspondencia uno a uno entre las soluciones, permitiendo aplicar directamente la fórmula de Separadores.
Los límites superiores, sin embargo, representan un salto importante en la dificultad y son una característica de la combinatoria de nivel intermedio a avanzado. Si las variables deben cumplir $x_i \le m$, no puedes simplemente "desplazar" la variable como lo haces con los límites inferiores. En su lugar, este escenario suele requerir el Principio de Inclusión-Exclusión (PIE). La estrategia consiste en calcular el número total de soluciones no negativas sin límites superiores, y luego restar las soluciones "malas" donde una o más variables rompen el límite superior (es decir, $x_i \ge m+1$). Esta interacción entre Separadores e Inclusión-Exclusión es una herramienta poderosa para resolver problemas complejos de distribución.
1. Separadores General (No negativos) El número de soluciones de $x_1 + \dots + x_k = n$ donde $x_i \ge 0$ es: $$ \binom{n+k-1}{k-1} $$
2. Soluciones con Límites Inferiores Para $x_1 + \dots + x_k = n$ sujeta a $x_i \ge a_i$ para todo $i=1, \dots, k$: Sea $A = \sum_{i=1}^k a_i$. El número de soluciones es: $$ \binom{n - A + k - 1}{k-1} $$
3. Soluciones con Límites Superiores (Inclusión-Exclusión) Para $x_1 + \dots + x_k = n$ sujeta a $0 \le x_i \le m$ para todo $i=1, \dots, k$: $$ \sum_{j=0}^k (-1)^j \binom{k}{j} \binom{n - j(m+1) + k - 1}{k-1} $$ Nota: En esta suma, cualquier coeficiente binomial $\binom{N}{R}$ donde $N < R$ se toma como $0$.
4. Caso Acotado General Para restricciones mixtas $a_i \le x_i \le b_i$, primero aplica el desplazamiento del límite inferior $y_i = x_i - a_i$ para reducir el problema a $0 \le y_i \le b_i - a_i$, y luego aplica la fórmula de límites superiores.
Teorema: El número de soluciones enteras de $x_1 + \dots + x_k = n$ sujeta a $0 \le x_i \le m$ está dado por $\sum_{j=0}^k (-1)^j \binom{k}{j} \binom{n - j(m+1) + k - 1}{k-1}$.
Demostración: La idea es usar el Principio de Inclusión-Exclusión (PIE).
Sea $S$ el conjunto de todas las soluciones enteras no negativas de $x_1 + \dots + x_k = n$ sin imponer las restricciones de límite superior. Por la fórmula estándar de Separadores, el tamaño de este conjunto es: $$ |S| = \binom{n+k-1}{k-1} $$
Define una "propiedad" $P_i$ como la condición de que la variable $x_i$ rompa el límite superior. Específicamente, $P_i$ es la condición $x_i > m$, que es lo mismo que $x_i \ge m+1$. Lo que hay que encontrar es el número de soluciones que no cumplen ninguna de las propiedades $P_1, P_2, \dots, P_k$.
Por el Principio de Inclusión-Exclusión, el número de soluciones válidas es: $$ N = \sum_{T \subseteq {1, \dots, k}} (-1)^{|T|} N(T) $$ donde $N(T)$ es el número de soluciones donde se rompen las restricciones del conjunto $T$ (es decir, $x_i \ge m+1$ para todo $i \in T$).
Sea $j = |T|$ el número de variables que rompen el límite superior. Sin perder generalidad, supón que las primeras $j$ variables rompen el límite: $$ x_1 \ge m+1, \quad x_2 \ge m+1, \quad \dots, \quad x_j \ge m+1 $$ Las $k-j$ variables restantes simplemente son no negativas ($x_i \ge 0$).
Para contar $N(T)$, aplica la transformación de límite inferior. Toma $y_i = x_i - (m+1)$ para $i \le j$, y $y_i = x_i$ para $i > j$. La ecuación queda así: $$ \sum_{i=1}^j (y_i + m + 1) + \sum_{i=j+1}^k y_i = n $$ $$ \sum_{i=1}^k y_i = n - j(m+1) $$ Como $y_i \ge 0$, aplica Separadores a esta ecuación transformada. El número de soluciones es: $$ \binom{(n - j(m+1)) + k - 1}{k-1} $$ Este valor solo depende del tamaño del conjunto $T$, que es $j$. Hay $\binom{k}{j}$ formas de elegir cuáles $j$ variables rompen la restricción.
Al sustituir esto de nuevo en la suma de PIE: $$ N = \sum_{j=0}^k (-1)^j \binom{k}{j} \binom{n - j(m+1) + k - 1}{k-1} $$ Nota que si $n - j(m+1) < 0$, el coeficiente binomial es 0, lo que termina la suma de forma natural cuando demasiadas variables se ven obligadas a pasarse de $n$.
$\square$