Domande relative al principio di inclusione-esclusione

Question

Oggi mi sono imbattuto per la prima volta nel principio di inclusione-esclusione. Credo di averlo capito, tuttavia quando ho provato a risolvere alcune domande su di esso, sono rimasto seriamente bloccato. Non sono riuscito a risolverne nessuno. Potresti suggerirmi alcune domande sull'escalation della difficoltà, in modo che io possa avere una buona comprensione dell'argomento in questione? Una delle domande è questa:https://math.stackexchange.com/questions/2765746/inclusion-exclusion-problem-sitting-arrangement , Era in un libro di matematica di un concorso greco e l'ho trovato anche su questo sito.

L'altra domanda non sono riuscita a trovarla su Internet, quindi la tradurrò:

Trova il numero di soluzioni dell'equazione $x_1+x_2+x_3=100$, se per ogni $3\ge i\ge1$, xi è un numero intero non negativo con $40\ge x_i$.

Ho trovato le soluzioni a entrambe queste domande, il motivo per cui le sto anche postando, è per dare una migliore comprensione al lettore del post (come sottolineato nei commenti), di quale livello di domande in inclusione- principio di esclusione mi stanno dando difficoltà

Answer 1

La seconda domanda, tradotta, non ha davvero bisogno di inclusione-esclusione; è abbastanza facile da usarehttps://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics), che è un'altra tecnica che vale la pena imparare (se non l'hai già fatto):

Scriviamo $u_i=40-x_i$, in modo che la restrizione sia $u_i\ge0$, quindi riscrivi l'equazione per risolverla come

$$u_1+u_2+u_3=20$$

(Questo viene da $100=x_1+x_2+x_3=(40-u_1)+(40-u_2)+(40-u_3)=120-(u_1+u_2+u_3)$, e poi spostando le cose). Stelle e barre ora indicano il numero di triple non negative che si sommano a $20$ è

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

Ad essere onesto, penso che avrei difficoltà a risolvere questo problema usando l'inclusione-esclusione; Sarei interessato a vedere se esiste un modo semplice per farlo.

Answer 2

Ecco l'approccio di inclusione-esclusione per il secondo problema, dove $k$ è il numero di $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 {red} { 231}. \ end {align} Il$$\binom{100-41k+3-1}{3-1}$$ parte proviene da un conteggio di stelle e barre delle soluzioni intere non negative a $x_1+x_2+x_3=100$ con $x_i \ge 41$ per $k$ specificato $i\in\{1,2,3\}$, equivalentemente, le soluzioni intere non negative a $y_1+y_2+y_3=100-41k$.