Cómo calcular el número de enteros solución de una ecuación lineal con restricciones?

Question

Si una ecuación es dada como este , $$x_1+x_2+...x_i+...x_n = S$$ y para cada una de las $x_i$ una restricción $$0\le x_i \le L_i$$ ¿Cómo podemos calcular el número de Enteros soluciones a este problema?

Answer 1

número de soluciones de la ecuación $$x_1+x_2+...x_i+...x_n = S$$ y para cada una de las $x_i$ una restricción $$0\le x_i \le L_i=s-1,i=1,2,...,n$$ es $$\sum_{i=0}^{n}(-1)^{i}\binom{n}{i}\binom{n+S-si-1}{n-1}$$ fórmula para el caso general, es más complicado.

Answer 2

Respuesta

La respuesta es el coeficiente de $y^S$ en el polinomio $A(y)=\prod_{i=1}^{n}{(\sum_{j=0}^{L_i}{y^j})}$.

Razonamiento

Definir $f(S)$ a ser el número entero de soluciones al problema que se suma a $S$ y cumplir con las demás restricciones. Entonces el ordinario de generación de función para$f(S)$: $$A(y)=\sum_{j=0}^{\infty}{f(j)y^j}$$

Definir $g_i(S)$ a ser el número de maneras en que sólo $x_i$ suma $S$. Entonces el ordinario de generación de función para cada una de las $g_i(S)$: $$A_i(y)=\sum_{j=0}^{\infty}{g_i(j)y^j}=\sum_{j=0}^{L_i}{y^j},i\in\{1,...,n\}$$

Podemos expresar $A(y)$ en términos de la $A_i(y)$:$$A(y)=\prod_{i=1}^{n}{A_i(y)}=\prod_{i=1}^{n}{(\sum_{j=0}^{L_i}{y^j})}$$

Ejemplo

$$x_1+x_2+x_3=S$$$$0\le x_1\le 4,0\le x_2\le 2,0\le x_3\le 1$$ $$A(y)=(1+y)(1+y+y^2)(1+y+y^2+y^3+y^4)$$$$=1+3x+5x^2+6x^3+6x^4+5x^5+3x^6+x^7$$

Así que no es de $1$ entero solución al $S=0$ o $S=7$, $3$ entero soluciones al $S=1$ o $S=6$, $5$ entero soluciones al $S=2$ o $S=5$, y $6$ entero soluciones al $S=3$ o $S=4$.