Encuentra el número de soluciones enteras de ecuación lineal

Question

Los que tenemos una ecuación. $$ x_1 + x_2 + x_3 + x_4 + x_5 =21 $$ $$x_i \ge 0$$ aditionnal condiciones son: $$ 0\le x_1 \le 3$$ $$ 1 \le x_2 \le4$$ $$ 15 \le x_3$$ La tarea es encontrar todos los enteros soluciones a la ecuación. Este es un típico ejemplo de inclusión-exclusión principio. Primer número de la solución, los cuales satisfacen $$ 15 \le x_3$$ and $$ 1 \le x_2$$ are found. According to the formula, we calculate all selections with repetitions from a set of 5 elements $$x_1,x_2,x_3,x_4,x_5$$ and the length of selection is $$21 -15 -1 = 5$$ hence: $$C(5 + 5 -1, 5 ) = 126$$

Asumir, que dado resultado es el conjunto universal de las soluciones en esta situación $U$ Ahora el uso de la inclusión-exclusión principio, opuesto condiciones se tienen en cuenta para $$x_1 \le 3$$ and $$x_2 \le4 $$ These conditions are respectively $$x_1\ge 4, x_2\ge 5$$ To find them calculate $$C_1(5+17-1,17) = 5985$$ and $$C_2(5+16-1,16) = 4845$$ Aviso, que estos resultados NO PUEDEN SER UTILIZADOS PARA ENCONTRAR LA RESPUESTA, ya que cada uno de ellos incluye el $x_3 < 15$ números y $C_1$ también incluye $x_2 < 1$ números (esto no satisface las restricciones iniciales). Por lo tanto, después de estas dos condiciones: 1) el Número de soluciones que satisfacen: $$ 4 \le x_1, 1 \le x_2, 15 \le x_3 $$ Esto es: $$C_3(5 + (21-4-1-15) -1, (21-4-1-15)) = 5$$ 2) el Número de soluciones que satisfacen: $$ 5 \le x_2, 15 \le x_3 $$ Esto es: $$C_4(5 + (21-5-15) -1, (21-5-15)) = 5$$

Tomando todos los cálculos en consideración, por el principio de inclusión-exclusión nos encontramos con que el resultado es: $$ C -C_3 - C_4= 126 -5 -5 = 116. $$

Answer 1

Su error es que se pierde la condición de $x_3\geq 15$. Usted todavía tiene que añadir que en la mezcla cuando se supone $x_1\geq 4$ y/o $x_2\geq 5$. En particular, hay no hay casos donde$x_3\geq 15$$x_1\geq 4$$x_2\geq 4$.

Dar un conjunto $U$, y dos subconjuntos $V,W$, se obtiene:

$$|U\setminus (V\cup W)| = |U|-|V| - |W| +|V\cap W|$$

Pero su $V,W$ no son subconjuntos - que, en casos donde el $x_3<15$, que su original recuento $U$ de los casos donde $x_3\geq 15$.

Yo uso la generación de funciones para resolver este problema.

Como usted indirectamente dado cuenta, usted puede pensar que estas condiciones como: $$y_1+y_2+y_3+y_4+y_5=5; y_i\geq 0\text{ and } y_1,y_2\leq 3.$$

Usted está tratando de encontrar el coeficiente de $x^5$ en la expresión:

$$(1+x+x^2+x^3)^2(1+x+x^2+\cdots)^3 = \frac{(1-x^4)^2}{(1-x)^5} = \frac{1-2x^4+x^8}{(1-x)^5}$$

Y $$\frac{1}{(1-x)^5} = \sum_{k=0}^{\infty} \binom{k+4}{4}x^k$$

Por lo que el coeficiente de $x^5$ en la:

$$(1-2x^4+x^8)\sum_{k=0}^{\infty} \binom{k+4}{4}x^k$$

es $\binom{9}{4} - 2\binom{5}{4}=116$.

Este es esencialmente el mismo resultado que obtendrá con la inclusión-exclusión. Tenemos $\binom{9}{4}=|U|$$\binom{5}{4}=|V|=|W|$, e $|V\cap W|=0$.