Cuántas soluciones para una ecuación con restricciones simples

Question

Estoy trabajando en una tarea en la que tengo que contar el número de soluciones para esta ecuación en particular: $$x_1+x_2+x_3+x_4=20$$ para los enteros no negativos con $x_1<8 $ y $x_2<6$

Soy consciente de que este tipo de tarea no es tan complicada, pero no entiendo muy bien la combinatoria en general.

Así que he intentado dos enfoques siguientes para conseguirlo.

En primer lugar he intentado sustituir la variable x:

$x_1+x_2+x_3+x_4=20 \Leftrightarrow y_1+y_2+y_3+y_4=34$

en el que $y_1=x_1+8$ y $y_2=x_2+6$ (caso $x_1=y_1-8$ y $x_2=y_1-6$ ) Siguiendo este enfoque, el número total de soluciones posibles sería

$${34+3 \choose 3} $$

Pero no estoy seguro de que sea la solución correcta.

El segundo enfoque consiste en sumar todos los posibles valores que $x_1$ y $x_2$ podría tomar, también $x_1=0,1,2,3,4,5,6,7$ y $x_2=0,1,2,3,4,5,6$ Y luego contar todas las posibilidades para cada una de las variables $${20 -x_1-x_2+1\choose 1}$$ y sumarlos así: $${21\choose 1}+{20\choose 1}+{19\choose 1}+{18\choose 1}+... $$ y así sucesivamente...

Estoy seguro de que acertaré con esta cifra, pero no me apetece sumar todas estas posibilidades. Tiene que haber una forma mejor y más elegante de tratar esto.

Mi profesor me dio una pista para que lo hiciera utilizando el complemento.

Answer 1

Una forma de verlo es la siguiente: El número de formas es sólo el coeficiente de $x^{20}$ en la expansión de $$(1+x+x^2+\cdots+x^7)(1+x+x^2+\cdots+x^5)(1+x+x^2+\cdots+x^{20})^{2}$$

Aquí, cada factor representa un término de su ecuación (aquí los he escrito en el mismo orden). Las potencias de $x$ en el factor son los valores que puede tomar la variable correspondiente. He limitado los dos últimos factores a una potencia máxima de $20$ ya que todos los términos son no negativos.

Ahora, la lógica detrás de esto es que cuando se multiplican dos potencias de $x$ los poderes se suman. El coeficiente de $x^{20}$ da el número de formas en las que podrías haber multiplicado varias potencias de cada factor para obtener una potencia total de $20$ . Observe que cada combinación de potencias de cada factor contribuye a un aumento de uno en el coeficiente y también representa una solución única de su ecuación. Así, el coeficiente de $x^{20}$ en la expansión binomial da la respuesta deseada.

Cada factor puede simplificarse utilizando las fórmulas de la suma de términos en una progresión geométrica. Entonces, el $(1-x)^{-n}$ Los términos pueden expandirse utilizando la expansión binomial, tras lo cual se puede encontrar fácilmente el coeficiente.

$$(1+x+x^2+\cdots+x^7)(1+x+x^2+\cdots+x^5)(1+x+x^2+\cdots+x^{20})^{2}=\frac{(1-x^8)(1-x^6)(1-x^{21})^2}{(1-x)^4}$$

Por lo tanto, hay que encontrar el coeficiente de $x^{20}$ en la expansión de $$(1-x^8)(1-x^6)(1-x)^{-4}$$ El $(1-x^{21})^2$ puede ignorarse, ya que los términos con coeficiente superior a $20$ no son motivo de preocupación. $$(1-x^8)(1-x^6)(1-x)^{-4}=(1-x^6-x^8+x^{14})(1+4x+10x^2+20x^3+\cdots+84x^{6}+\cdots+455x^{12}+\cdots+680x^{14}+\cdots+1771x^{20}+\cdots+\binom{n+3}{n}x^n+\cdots)$$ El coeficiente es así: $$1771-455-680+84=720$$

Answer 2

Para determinar el número de soluciones de la ecuación $$x_1 + x_2 + x_3 + x_4 = 20 \tag{1}$$ en los enteros no negativos sujetos a las restricciones $x_1 < 7$ y $x_2 < 6$ restamos el número de soluciones en las que $x_1 > 7$ o $x_2 > 5$ del número de soluciones de la ecuación.

Una solución particular de la ecuación 1 corresponde a la colocación de tres signos de suma en una fila de $20$ los. Por ejemplo, $$1 1 1 1 + 1 1 1 1 1 + 1 1 1 1 1 1 + 1 1 1 1 1$$ corresponde a la solución $x_1 = 4$ , $x_2 = 5$ , $x_3 = 6$ y $x_4 = 5$ , mientras que $$+ 1 1 1 1 1 1 1 1 1 + 1 1 1 1 1 1 1 + 1 1 1 1$$ corresponde a la solución $x_1 = 0$ , $x_2 = 9$ , $x_3 = 7$ y $x_4 = 4$ . Así, el número de soluciones de la ecuación 1 es el número de formas en que se pueden insertar tres signos de adición en una fila de $20$ que es $$\binom{20 + 3}{3}$$ ya que debemos elegir qué tres de los $23$ símbolos ( $20$ y $3$ signos de adición) serán signos de adición.

Supongamos que $x_1 > 7$ . Entonces $y_1 = x_1 - 8$ es un número entero no negativo. Sustituyendo $y_1 + 8$ para $x_1$ en la ecuación 1 da como resultado \begin {align*} y_1 + 8 + x_2 + x_3 + x_4 & = 20 \\ y_1 + x_2 + x_3 + x_4 & = 12 \tag {2} \end {align*} La ecuación 2 es una ecuación en los enteros no negativos con

$$\binom{12 + 3}{3} = \binom{15}{3}$$

soluciones.

Supongamos que $x_2 > 5$ . Entonces $y_2 = x_2 - 6$ es un número entero no negativo. Sustituyendo $y_2 + 6$ para $x_2$ en la ecuación 1 da como resultado \begin {align*} x_1 + y_2 + 6 + x_3 + x_4 & = 20 \\ x_1 + y_2 + x_3 + x_4 & = 14 \tag {3} \end {align*} La ecuación 3 es una ecuación en los enteros no negativos con

$$\binom{14 + 3}{3} = \binom{17}{3}$$

soluciones.

Si al número de soluciones de la ecuación 2 y de la ecuación 3 le restamos el número de soluciones de la ecuación 1, habremos restado aquellas soluciones en las que $x_1 > 7$ y $x_2 > 5$ dos veces. Así, debemos sumar el número de soluciones en las que $x_1 > 7$ y $x_2 > 5$ .

Supongamos que $x_1 > 7$ y $x_2 > 5$ . Entonces $y_1 = x_1 - 8$ y $y_2 = x_2 - 6$ son enteros no negativos. Sustituyendo $y_1 + 8$ para $x_1$ y $y_2 + 6$ para $x_2$ en la ecuación 1 da como resultado \begin {align*} y_1 + 8 + y_2 + 6 + x_3 + x_4 & = 20 \\ y_1 + y_2 + x_3 + x_4 & = 6 \tag {4} \end {align*} La ecuación 4 es una ecuación en los enteros no negativos con

$$\binom{6 + 3}{3} = \binom{9}{3}$$

soluciones.

Por el Principio de inclusión-exclusión el número de soluciones de la ecuación 1 en los enteros no negativos sujeto a las restricciones de que $x_1 < 7$ y $x_2 < 6$ es

$$\binom{23}{3} - \binom{15}{3} - \binom{17}{3} + \binom{9}{3}$$

Answer 3

La forma clásica de hacerlo es contar las soluciones sin condiciones, y luego utilizar la inclusión-exclusión para tratar los casos que violan.

Así que si $A$ es el conjunto de todas las soluciones no negativas de $x_1+x_2+x_3+x_4=20$ y $A_1$ es el conjunto de tales soluciones con $x_1\geq 8$ y $A_2$ es el conjunto de soluciones con $x_2\geq 6$ entonces el conjunto que busca contar es $A\setminus(A_1\cup A_2)$ y:

$$\left|A\setminus(A_1\cup A_2)\right|=|A|-|A_1|-|A_2|+|A_1\cap A_2|$$

Por inclusión-exclusión. Ahora, cada uno de estos términos es mucho más fácil de calcular. Por ejemplo, $A_1\cap A_2$ es el conjunto de soluciones de $x_1+x_2+x_3+x_4=20$ con $x_1\geq 8,x_2\geq 6$ que es igual al conjunto de soluciones no negativas de $y_1+y_2+x_3+x_4=20-14=6$ .