¿Cómo encontrar el número de soluciones como esta?
$$x_1 + x_2 + x_3 + x_4 = 32$$
donde $0 \le x_i \le 10$.
¿Cuál es el enfoque generalizado para él?
Respuestas
¿Demasiados anuncios?
Primero se calcula el número de soluciones en enteros no negativos sin preocuparse por el límite superior de $10$ en cada variable. Este es un estándar de estrellas-y-bares problema, razonablemente bien explicado en el artículo de la Wikipedia. A continuación, utilice la inclusión-exclusión de principio a deshacerse de los no deseados soluciones.
En este caso, el primer paso que da la cifra preliminar de $$\binom{32+4-1}{4-1}=\binom{35}3=6545\;.$$
Ahora, contar el número de soluciones que permiten a $x_1$ demasiado grande. Esto significa que $x_1\ge 11$, por lo que el exceso de $11$ $x_1$ más que los valores de $x_2,x_3$, e $x_4$ debe agregar a a $32-11=21$. Cada uno de estos no deseados de las soluciones, por tanto, corresponde a una solución en los enteros no negativos a la ecuación de $y_1+y_2+y_3+y_4=21$, y hay $$\binom{21+4-1}{4-1}=\binom{24}3=2024$$ of those. In fact there are $2024$ unwanted solutions for each of the four variables, so our next approximation is $6545-4\cdot2024=-1551$ soluciones.
Por supuesto, esto obviamente no es la correcta. El problema es que algunas de las soluciones que superen el límite de $10$ sobre más de una variable. Cada solución que supera el límite en dos variables fue eliminado dos veces cuando nos resta $4\cdot 2024$ y por lo tanto tiene que ser agregado en. Considere la posibilidad de una solución que tiene tanto $x_1$ $x_2$ mayor que $10$. Entonces el exceso en $x_1$, el exceso en $x_2$ y los valores de $x_3$ $x_4$ deben sumar a $32-2\cdot11=10$, por lo que estamos esencialmente contar soluciones en enteros no negativos a la ecuación de $y_1+y_2+y_3+y_4=10$, de los cuales hay $$\binom{10+4-1}{4-1}=\binom{13}3=286\;.$$ There are $\binom42=6$ pairs of variables, so we must add back in $6\cdot286=1716$ to get a better approximation of $-1551+1716=165$ soluciones.
Es imposible para más de dos variables para superar sus cuotas, ya que $3\cdot11=33>32$. Por lo tanto, no se necesitan correcciones, y la respuesta final es $165$ soluciones reunión de la original de las condiciones de contorno.
Vel
Puntos
66
Si se considera la siguiente función $$ f_{\rm dim}(\epsilon)=\left(\frac{1-\epsilon^{11}}{1-\epsilon}\right)^{4}, $$ y ampliar a $\epsilon=0$, entonces el coeficiente delante de $\epsilon^{32}$ le dará el resultado correcto, 165.
Explicación de la razón por la que esto funciona es dado en mi respuesta a Esta pregunta.
El método puede ser, obviamente, aplicado al caso genérico: Supongamos que hay ecuación $$\sum_{i=1}^n x_i=M$$ and we demand constraints $\lambda_i\leq x_i\leq \Lambda_i$. La pregunta es ¿cuántas soluciones hay?. La respuesta es considerar
$$ f_{\rm dim}(\epsilon)=\prod_{i=1}^n\frac{\epsilon^{\lambda_i}-\epsilon^{\Lambda_i+1}}{1-\epsilon}\,, $$ ampliar esta función en $\epsilon=0$ y encontrar el coeficiente de expansión a $\epsilon^{M}$.
Definitivamente, este método es un enfoque muy eficaz para el uso en una computadora, y mucho más rápido que generar todas las permutaciones posibles, como fue sugerido en otra respuesta a su pregunta.
Para su caso en particular, este método también puede ser utilizado para realizar un cálculo de las manos (aunque podría no ser el caso en el genérico de la situación). La necesaria coeficiente está dada por la integral de contorno $\oint\frac{d\epsilon}{2\pi\,i}\frac{f_{\rm dim}(\epsilon)}{\epsilon^{33}}$ alrededor del origen. Pero esta integral también puede ser calculada por el residuo en $\epsilon=\infty$ (tenga en cuenta que en $\epsilon=1$ no hay polo). Para el propósito de encontrar $1/\epsilon$ plazo en el gran $\epsilon$ epxansion, el reemplazo de la $1-\epsilon^{11}\to-\epsilon^{11}$ se puede utilizar:
$$ \left(\frac{1-\epsilon^{11}}{1-\epsilon}\right)^{4}\frac 1{\epsilon^{33}}\simeq\epsilon^{11\times 4-33}\frac 1{(1-\epsilon)^4}=\epsilon^7\left(\frac 1{1-\epsilon^{-1}}\right)^4\a\epsilon^7\times\epsilon^{-8}\binom{8+4-1}{4-1}=\frac{165}{\epsilon} $$ Después de todo, la respuesta es calculada por un único coeficiente Binomial $\binom{8+4-1}{4-1}$. Esto nos da una posibilidad de adivinar un buen truco. Considere la posibilidad de una solución de la ecuación
$$ y_1+y_2+y_3+y_4=8 $$ con la única restricción $y_i\geq 0$. A continuación, $x_i=10-y_i$ va a ser una solución a la ecuación original. Es fácil comprobar que este es uno de un mapa (con límite de requisitos), por lo $\binom{8+4-1}{4-1}$, el número de soluciones para la ecuación en $y$'s, es la respuesta deseada.
bentsai
Puntos
1886
En GAP, puede ser computados por medio de:
R:=RestrictedPartitions(32,[0..10],4);
S:=Union(List(R,r->Arrangements(r,4)));;
Size(S);
que da 165.
Tenga en cuenta que el primer paso genera desordenadas particiones de 32 en 4 partes, que $R$. Entonces necesito permutar en todas las formas posibles, y su unión para crear todas las posibilidades, $S$.
