Preguntas relacionadas con el principio de inclusión-exclusión

Question

Hoy me encontré con el principio de inclusión-exclusión por primera vez. Creo que lo he entendido, sin embargo, cuando intenté resolver algunas preguntas, me quedé muy atascado. No pude resolver ninguno de ellos. ¿Podría sugerir algunas preguntas de dificultad creciente, de modo que pueda comprender bien el tema en cuestión? Una de las preguntas es esta:https://math.stackexchange.com/questions/2765746/inclusion-exclusion-problem-sitting-arrangement Estaba en un libro de matemáticas de concurso griego y también lo encontré en este sitio.

La otra pregunta no la pude encontrar en Internet, así que la traduciré:

Encuentra el número de soluciones de la ecuación $x_1+x_2+x_3=100$, si por cada $3\ge i\ge1$, xi es un número entero no negativo con $40\ge x_i$.

He encontrado las soluciones a ambas preguntas, la razón por la que las estoy publicando también es para brindar una mejor comprensión al lector de la publicación (como se señala en los comentarios), de qué nivel de preguntas en la inclusión. el principio de exclusión me está dando dificultades

Answer 1

La segunda pregunta, traducida, realmente no necesita inclusión-exclusión; es bastante fácil de hacer usandohttps://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics), que es otra técnica que vale la pena aprender (si aún no lo ha hecho):

Vamos a escribir $u_i=40-x_i$, de modo que la restricción sea $u_i\ge0$, y luego reescribe la ecuación para resolver como

$$u_1+u_2+u_3=20$$

(Esto viene de $100=x_1+x_2+x_3=(40-u_1)+(40-u_2)+(40-u_3)=120-(u_1+u_2+u_3)$y luego mover cosas.) Las estrellas y las barras ahora dicen el número de triples no negativos sumando $20$ es

$${22\choose2}={22\cdot21\over2}=231$$

Para ser honesto, creo que me costaría mucho resolver este problema utilizando la inclusión-exclusión; Me interesaría ver si hay una manera fácil de hacerlo.

Answer 2

Aquí está el enfoque de inclusión-exclusión para el segundo problema, donde $k$ es el numero de $i\in\{1,2,3\}$ con $x_i \ge 41$: \ begin {align} \ sum_ {k = 0} ^ 2 (-1) ^ k \ binom {3} {k} \ binom {100-41k + 3-1} {3-1} & = \ binom { 102} {2} -3 \ binom {61} {2} +3 \ binom {20} {2} \\ & = 5151-3 \ cdot 1830 + 3 \ cdot 190 \\ & = \ color {rojo} { 231}. \ end {align} El$$\binom{100-41k+3-1}{3-1}$$ parte proviene de un recuento de estrellas y barras de las soluciones enteras no negativas para $x_1+x_2+x_3=100$ con $x_i \ge 41$ para $k$ especificado $i\in\{1,2,3\}$, de manera equivalente, las soluciones enteras no negativas para $y_1+y_2+y_3=100-41k$.