La complejidad de las soluciones de recuento de $x_1 + \dots + x_m = N$ en enteros no negativos bajo las restricciones

Question

Considere la ecuación $$x_1 + \dots + x_m = N$$ donde $x_1,\dots,x_m \ge 0$ y bajo las restricciones adicionales $x_k \le a_k$  para $k=1,2,\dots,m$ .

Estoy interesado en saber si el número de soluciones a (1) se puede encontrar en tiempo sub-exponencial con respecto a. $m$ .

Una forma de resolverlo sería disminuir recursivamente el número de restricciones restando el número de soluciones con restricciones $0 \le x_1 \le a_1, \dots, 0 \le x_{m-1} \le a_{m-1}, x_{m-1} > a_{m-1}$ de las soluciones sin la restricción de $x_{m-1}$ . Dado que las restricciones del tipo $x_j > a_j$  se puede tratar sustituyendo $x_j + a_j + 1$ para $x_j$ y dado que existe una fórmula cerrada para el caso sin restricciones en absoluto, conseguiremos el trabajo en aproximadamente $2^m$ pasos. Esto es básicamente el principio de inclusión y exclusión.

Answer 1

Se desea el coeficiente de $y^N$ en $$(1+y+\cdots+y^{a_1})\times\cdots\times(1+y+\cdots+y^{a_m})$$ Reescribir el producto como $$(1-y^{a_1+1})\times\cdots\times(1-y^{a_m+1})(1-y)^{-m}$$ Ampliar $$(1-y)^{-m}=\sum_0^N{n+m-1\choose m-1}x^n+{\rm\ higher\ order\ terms}$$ Ahora multiplique a su vez por $1-y^{a_1+1},\dots,1-y^{a_m+1}$ . Siempre se pueden descartar los términos en $y^s$ con $s\gt N$ a lo largo del camino.