El problema de contar las soluciones $(a_1,a_2,\ldots,a_n)$ con un número entero $a_i\geq0$ para $i\in\{1,2,\ldots,n\}$ tal que $$a_1+a_2+a_3+....a_n=N$$ puede resolverse con un argumento de estrellas y barras. ¿Cuál es la solución si se añade la restricción de que $a_i\leq r_i$ para ciertos enteros $r_1,\ldots,r_n$ ?
Por ejemplo, para $n=3$ , $N=6$ y $(r_1,r_2,r_3)=(3,3,2)$ la tupla $(a_1,a_2,a_3)=(2,3,1)$ es una solución, pero $(2,1,3)$ no es una solución porque $a_3=3>2=r_3$ .
Hasta donde yo sé, no existe una fórmula cerrada para este problema general, pero hay una fórmula que permite calcular el número de soluciones en un número de operaciones independiente de $N$ . Consideremos primero el caso de que todos los límites sean iguales $r_1=r_2=\cdots=r_n=r$ . Entonces el número es el coeficiente de $X^N$ en el polinomio $(1+X+\cdots+X^r)^n$ . Escribiendo esto como una función racional de $~X$ $$ (1+X+\cdots+X^r)^n=\left(\frac{1-X^{r+1}}{1-X}\right)^n=\frac{(1-X^{r+1})^n}{(1-X)^n} $$ el coeficiente de $X^k$ en el numerador es cero a menos que $k$ es un múltiplo $q(r+1)$ de $r+1$ , en cuyo caso es $(-1)^q\binom nq$ y el coeficiente de $X^l$ en la inversa del denominador es $(-1)^l\binom{-n}l=\binom{l+n-1}l$ que es cero a menos que $l\geq0$ y, en caso contrario, igual a $\binom{l+n-1}{n-1}$ . Queda por sumar todos los $k+l=N$ , lo que da $$ \sum_{q=0}^{\min(n,N/(r+1))}(-1)^q\binom nq\binom{N-q(r+1)+n-1}{n-1}, $$ donde la suma se trunca para garantizar que $N-q(r+1)\geq0$ (la condición $l\geq0$ ). Aunque la suma parece complicada, tiene como máximo $n+1$ términos fácilmente calculables, para cualquier $~N$ . A modo de ejemplo, el coeficiente de $n=5$ , $r=100$ y $N=243$ se calcula fácilmente que es $62018665$ . Un punto interesante a destacar es que si la suma no se hubiera truncado, entonces el resultado habría sido claramente una función polinómica de $~N$ de grado ${}<n$ (porque los coeficientes binomiales $\binom xk$ son funciones polinómicas de $~x$ de grado $~k$ ). Pero por un lado esa función polinómica da los valores exactos de este problema para $N\geq n(r+1)$ donde no se produce ningún truncamiento, mientras que por otro lado, dado el problema original, esos valores son todos $~0$ por lo que la función polinómica será idéntica a cero. Así que una fórmula alternativa para el resultado es calcular el negativo de los términos truncados, cuya fórmula se convierte después de un poco de masaje $$ \sum_{q=\lceil\frac{N+n}{r+1}\rceil}^n (-1)^{n-q}\binom nq\binom{q(r+1)-1-N}{n-1}, $$ que es más fácil de usar para grandes $~N$ . Por ejemplo, en el ejemplo anterior esta fórmula da un solo término $\binom{78}4=1426425$ para $N=426$ es el mismo valor que se obtiene para $N=74=500-426$ (de la primera fórmula), lo que puede entenderse por el hecho de que los "restos" $r_i-a_i$ suman $nr-N$ .
En el caso general de límites distintos $r_i$ El enfoque es el mismo, pero la fórmula se vuelve un poco confusa. En lugar de un numerador $(1-X^{r+1})^n$ se obtiene un producto $P=(1-X^{r_1+1})\ldots(1-X^{r_n+1})$ que en general tiene más términos no nulos (el número de términos puede ser hasta $\min(\Sigma r_i+n+1,2^n)$ ), pero que se puede calcular de una vez por todas. Con $P=\sum_ic_iX^{e_i}$ la fórmula del resultado es $$ \sum_ic_i\binom{N-e_i+n-1}{n-1}, $$ que sigue siendo una suma de varios términos independientes de $~N$ . Pero, por supuesto, el cálculo del polinomio $\frac P{(1-X)^n}$ de antemano, y luego para cualquier $N$ sólo buscando el coeficiente de $X^N$ es otro tiempo esencialmente constante (en $N$ ).
Para futuras referencias, para las personas que no están familiarizadas con las funciones generadoras, aquí hay una solución utilizando el principio de exclusión de la inclusión.
Ignorar la restricción $a_i\le r_i$ el número de soluciones es $\binom{N+n-1}{n-1}$ por estrellas y barras. Para incorporar estas restricciones, restamos las soluciones "malas" en las que algunos $a_i>r_i$ . Para contar las soluciones en las que $a_1>r_1$ En cambio, contamos las soluciones de la ecuación $$ (a_1-r_1-1)+a_2+a_3+\dots+a_n=N-r_1-1 $$ Ahora, todos los sumandos del lado izquierdo son enteros no negativos, por lo que el número de soluciones es $\binom{N-r_1-1+n-1}{n-1}$ . Por lo tanto, restamos $\binom{N-r_i-1+n-1}{n-1}$ para cada $i=1,2,\dots,n$ .
Sin embargo, las soluciones con dos variables que eran demasiado grandes se han restado dos veces, por lo que hay que volver a sumarlas. Soluciones en las que $a_i>r_i$ y $a_j>r_j$ se puede contar restando $r_i+1$ de $a_i$ y $r_j+1$ de $a_j$ dejando una lista de enteros que suman $N-(r_i+1)-(r_j+1)$ cuyo número es $\binom{N-(r_i+1)-(r_j+1)+n-1}{n-1}$ .
A continuación, debemos corregir las soluciones con tres variables que son demasiado grandes, luego cuatro, y así sucesivamente. Esto puede tratarse sistemáticamente utilizando el principio de exclusión de la inclusión. El resultado es $$ \sum_{S\subseteq \{1,2,\dots,n\}}(-1)^{|S|}\binom{N+n-1-\sum_{i\in S}(r_i+1)}{n-1} $$ En este caso, definimos $\binom{m}k=0$ siempre que $m<0$ .
Para el caso especial $r_1=r_2=\dots=r_n=r$ donde el límite superior es el mismo para cada variable, el resultado es $$ \sum_{k=0}^{\lfloor N/(r+1) \rfloor}(-1)^k\binom{n}k\binom{N-k(r+1)+n-1}{n-1}. $$
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
