Contar el número de enteros soluciones a $x_1+x_2+\cdots+x_5=36$

Question

Cómo contar el número de enteros soluciones a $x_1+x_2+\cdots+x_5=36$ tal que $x_1\ge 4,x_3 = 11,x_4\ge 7$

Y ¿qué hay de $x_1\ge 4, x_3=11,x_4\ge 7,x_5\le 5$

En ambos casos, $x_1,x_2,x_3,x_4,x_5$ deben ser números enteros no negativos.

Hay una fórmula general para calcular cosas como esta?

Answer 1

(Supongo que te refieres a de la $x_i$ a ser no negativo, de lo contrario hay infinitamente muchas soluciones.)

Supongamos que no tenía restricciones en la $x_i$. El problema es abordado por las "Estrellas y Barras" método (o, si usted no desea contar el orden de los sumandos, la Función de Partición).

Ahora, la primera pregunta puede ser reducida a una cuestión sin limitaciones preguntando:

¿Cuál es el número de número entero no negativo soluciones a $x_1 + x_2 + x_4 + x_5 = 14$?

Yo lo que hice fue establecer $x_3 = 11$ y restar 11 de la derecha y retire $x_3$ de consideración, ya que podemos considerar a $x_3$ como una constante.

Para$x_1$$x_4$, restar 4 y 7, respectivamente, de la parte derecha. Ahora nos preocupamos sólo de que $x_1 \geq 0$$x_4 \geq 0$. En otras palabras, queremos que el número de entero no negativo soluciones a $x_1 + x_2 + x_4 + x_5 = 14$.

Para cuidar de una restricción como $x_5 \leq 5$, en primer lugar, encontrar el número de soluciones sin restricciones en $x_5$. A continuación, busque el número de soluciones con $x_5 \geq 6$. Resta el último de la antigua.

Answer 2

Aquí es un acercamiento a la comprensión de su problema en una mayor generalidad.

Supongamos que queremos contar el número de no-negativa y ordenó entero de soluciones de la ecuación de Diophantine $x_1 + x_2 + x_3 + x_4 + x_5 = 36$ con las siguientes restricciones adicionales: $x_1 \geq 4$, $x_3 = 11$ y $x_4 \geq 7$. En primer lugar, como mi colega Mike sugiere, vamos a restar $x_3$ desde ambos lados. Luego, podemos contar: $x_1 + x_2 + x_4 + x_5 = 25$ dijo restricciones.

Yo prefiero pensar acerca de este problema combinatorio en términos de celosía puntos de dilatación de polytopes. Las restricciones de desigualdad $x_1 + x_2 + x_4 + x_5 \leq R$ representa el número de no-negativo celosía puntos de la $R$-se dilatan de la polytope $\mathbf{conv}(\mathbf{0}, \mathbf{e}_1, \mathbf{e}_2, \mathbf{e}_3, \mathbf{e}_4)$, que es la delimitada por una $4$-simplex o pentachoron y los límites naturales de la positiva orthant, donde $\mathbf{e}_i$ representa el$i^{\text{th}}$$\mathbb{R}^{4}$. Por simplicidad, vamos a llamar a este objeto simplicial $4$-polytope $P$.

Es claro que el número no negativo soluciones de $x_1 + x_2 + x_4 + x_5 = R$ se encuentra considerando la desigualdad $R - 1 < x_1 + x_2 + x_4 + x_5 \leq R$ lo cual puede determinarse simplemente restando el número de celosía de puntos de dos consecutivos dilata de la misma pentachoron. Dicho esto, el número de no-negativo entramado de puntos de una $R$-se dilatan de $P$ es la suma iterada, \begin{align} N(R) = \sum_{i_1 = 0}^{R} \sum_{i_2 = 0}^{R - i_1} \sum_{i_3 = 0}^{R - i_1 -i_2} \sum_{i_4 = 0}^{R - i_1 -i_2 -i_3} 1 = \binom{R + 4}{R}. \end{align} Así que, sin restricciones, tenemos el siguiente número de no-negativo soluciones: \begin{align} \binom{R+4}{R} - \binom{R + 3}{R - 1}. \end{align} Para dar cuenta de las restricciones, se modifican los diversos límites de la recapitulación, en consecuencia, \begin{align} N(R) = \sum_{i_1 = 4}^{R} \sum_{i_2 = 0}^{R - i_1} \sum_{i_3 = 7}^{R - i_1 -i_2} \sum_{i_4 = 0}^{ R-i_1 - i_2 - i_3} 1. \end{align} Así que la respuesta a tu primera pregunta (sin restricción en $x_5$) es, por tanto,$N(25) - N(24)$,$680$. Para dar cuenta de la restricción de la $x_5$, además, modificar el interior de suma, \begin{align} N(R) = \sum_{i_1 = 4}^{R} \sum_{i_2 = 0}^{R - i_1} \sum_{i_3 = 7}^{R - i_1 -i_2} \sum_{i_4 = 0}^{ \min(5, R-i_1 - i_2 - i_3)} 1. \end{align} La respuesta a la segunda pregunta es, por tanto,$N(25) - N(24)$,$515$.

Para calcular las soluciones de forma explícita, use el siguiente código de mathematica:

FindInstance[x1 + x2 + x4 + x5 == 25 && x1 >= 4 && x2 >= 0 && x4 >= 7 && x5 >= 0, {x1, x2, x4, x5}, Enteros, 1000]}

FindInstance[x1 + x2 + x4 + x5 == 25 && x1 >= 4 && x2 >= 0 && x4 >= 7 && 5 >= x5 >= 0, {x1, x2, x4, x5}, Enteros, 1000]}

Calcular el "Longitud[]" de la salida y se puede comprobar que no hay, de hecho, $680$ $515$ soluciones integrales, respectivamente.

Answer 3

Lo primero es lo primero. Tomemos $x_3$ fuera de la ecuación, lo que nos deja con $x_1+x_2+x_4+x_5=25$. Para el primer problema, voy a asumir que $x_2$ $x_5$ son no-negativos, de lo contrario, creo que vamos a tener infinitas soluciones. Sabemos $x_1$ es de al menos 4 e $x_4$ es de al menos 7, por lo que nos da un total de 14 para distribuir a los 4 diferentes variables.

Para representar la distribución de estos 14 puntos, vamos a usar una cadena de 0's y 1's. Así, por ejemplo, 00010001000100000 representa el $x_1=4+3=7,x_2=3,x_4=7+3=10$, e $x_5=5$. El 1 son los divisores. Así tenemos 14 0 para el 14 puntos y 3 divisores. Así que tenemos una cadena de tamaño 17 y queremos establecer 3 de los personajes a 1. El número de cadenas de este tipo es $\binom {17}{3}$.

Answer 4

$\infty$, si usted no tiene ninguna restricción en $x_2$ $x_5$ otros de que son números enteros: tenga en cuenta que usted puede agregar siempre $1$ a uno de estos y restar $1$ a partir de la otra. O quisiste decir no negativo (o positivo) enteros?