¿Entre enteros no negativos para formar una suma con restricciones?

Question

¿Cómo lo resuelvo?

Número de soluciones no negativas de $x_1 + x_2 + x_3 + x_4 = 4$ donde $0 \le x_i \le 3$ ?

¿Cuál es la técnica general? Ya conozco la técnica para $j \le x_i$ pero no tienen idea de las restricciones de los límites superiores.

Answer 1

Si se calcula el polinomio $(1+X+X^2+X^3)^4$ entonces el coeficiente de $X^n$ será el número de soluciones del problema con el lado derecho $n$ (así $n=4$ da su respuesta $31$ aquí).

Answer 2

Se trata de una forma sencilla de selección de un conjunto múltiple. La versión general tendría límites variables para cada $x_i$ . Puede utilizar un enfoque de inclusión-exclusión para enumerar las posibilidades:

• Calcula el número de combinaciones como si no hubiera límites máximos
• Calcular el número de combinaciones que rompen la restricción para cada variable individual
• Calcular el número de combinaciones que rompen la restricción para los pares de variables
• Calcular el número que rompe la restricción para las combinaciones superiores
• Combinar los resultados anteriores según las reglas de inclusión-exclusión

Obviamente, en este caso sólo estamos eliminando el $x_i= 4$ casos, por lo que se puede utilizar un argumento más sencillo.