Principio de inclusión-exclusión: número de soluciones enteras de las ecuaciones

Question

El problema es:

Hallar el número de soluciones enteras de la ecuación $$ x_1 + x_2 + x_3 + x_4 = 15 $$ satisfaciendo $$ \begin{align} 2 \leq &x_1 \leq 4, \\ -2 \leq &x_2 \leq 1, \\ 0 \leq &x_3 \leq 6, \text{ and,} \\ 3 \leq &x_4 \leq 8 \>. \end{align} $$

He leído algunos artículos sobre esta cuestión, pero ninguno lo explica con suficiente claridad. Estoy especialmente confuso cuando hay que disminuir la cantidad total de soluciones de la ecuación -sin tener en cuenta las restricciones- a partir de las soluciones que no queremos. ¿Cómo encontramos la intersección de los conjuntos que no queremos? De cualquier manera, en ayudarme con esto, por favor explique este paso.

Answer 1

No estoy seguro de poder ampliar las insinuaciones de PEV en un comentario, así que lo convertiré en una respuesta.

Es necesario conocer el número de soluciones de $$u_1+u_2+\dots+u_r=n$$ cuando la única restricción de las variables es que sean números enteros no negativos. Imagine $n+r-1$ puntos en una línea, y círculo $r-1$ de ellos. Los puntos sin círculo son $n$ en número, y los rodeados dividen a los no rodeados en $r$ grupos (algunos de los cuales pueden estar vacíos), por lo que se obtiene $r$ enteros no negativos que suman $n$ . Así que la pregunta es, ¿de cuántas maneras se puede elegir qué $r-1$ de la $n+r-1$ ¿puntos para rodear? Por desgracia, PEV escribió 18-elegir-3, donde creo que lo que se quiere es 15-elegir-3, pero ahora deberías ver cómo conseguir esa parte de la respuesta.

Luego preguntas cómo utilizar la inclusión-exclusión. No queda claro si lo que quieres decir es que no ves cómo obtener una fórmula para el tamaño de la unión utilizando inc-excl, o si lo que quieres decir es que puedes escribir una fórmula pero no ves cómo encontrar los tamaños de las $A_i$ y las diversas intersecciones que surgen, así que es un poco difícil ayudarte aquí. Asumiré que es la segunda sugerencia. Así que para PEV $A_1$ , dejemos que $v_1=y_1-3$ entonces tienes $v_1+y_2+y_3+y_4=9$ y las variables son no negativas, por lo que se aplica el párrafo anterior. Del mismo modo, para la intersección de $A_1$ y $A_2$ , dejemos que $v_1=y_1-3$ y $v_2=y_2-4$ por lo que se obtiene $v_1+v_2+y_3+y_4=5$ con todas las variables no negativas.

¿Puedes seguir a partir de ahí?

Answer 2

Sea $y_1 = x_1-2$ , $y_2 = x_2+2$ , $y_3 = x_3$ y $y_4 = x_4-3$ . Entonces se quiere encontrar el número de soluciones enteras de $y_1+y_2+y_3+y_4 = 12$ donde $0 \leq y_1 \leq 2$ , $0 \leq y_2 \leq 3$ , $0 \leq y_3 \leq 6$ y $0 \leq y_4 \leq 5$ . Sea $A_1$ sea el conjunto de soluciones tales que $y_1 \geq 3$ , $A_2$ sea el conjunto de soluciones tales que $y_2 \geq 4$ , $A_3$ sea el conjunto de soluciones tales que $y_3 \geq 7$ y $A_4$ sea el conjunto de soluciones tales que $y_4 \geq 6$ . Sea $S$ sea el número total de soluciones no negativas sin restricciones. Entonces $|S|= \binom{15}{3}$ . Así que quieres encontrar $|S \ \backslash \ (A_1 \cup A_2 \cup A_3 \cup A_4)|$ . Así que utiliza la inclusión-exclusión para obtener $|A_1 \cup A_2 \cup A_3 \cup A_4|$ .

Answer 3

Si no entiendes la pregunta más grande, empieza primero por lo más pequeño.

• ¿Cuántas soluciones para $x_1 + x_2 = 15$ ¿Sin restricciones? (infinito por supuesto)

• ¿Cuántas soluciones $0\le x_1$ , $0\le x_2$ ?

• ¿Cuántas soluciones $6\le x_1$ , $0\le x_2$ ?

• ¿Cuántas soluciones $6\le x_1$ , $6\le x_2$ ? (estas últimas preguntas aún no dicen nada sobre la inclusión-exclusión)

• ¿Cuántas soluciones $0\le x_1\le 5$ , $0\le x_2$ ? Pista: excluir el complemento. Este es el primer paso de la exclusión.

• ¿Cuántas soluciones $0\le x_1\le 5$ , $0\le x_2\le7$ ? Pista: excluya los dos complementos, pero vuelva a incluir donde se solapan esos dos complementos (la intersección de esos dos rangos excluidos - qué es), porque excluyó la intersección dos veces.

Esto es lo esencial. Ahora se pone más difícil, porque hay que hacerlo para 4 variables no sólo 2. Pero ese es el ejercicio, encontrar la manera de gestionar la inclusión / exclusión / a continuación, incluyendo de nuevo de lo que tiró demasiado de / a continuación, excluyendo de nuevo que poco desordenado en ese último paso.