Questions relatives au principe d'inclusion-exclusion

Question

Aujourd'hui, je suis tombé sur le principe d'inclusion-exclusion pour la première fois. Je crois l'avoir compris, mais quand j'ai essayé de résoudre quelques questions à ce sujet, je suis resté gravement coincé. Je n'ai pu résoudre aucun d'entre eux. Pourriez-vous s'il vous plaît suggérer quelques questions de difficulté croissante, afin que je puisse avoir une bonne compréhension du sujet à portée de main? L'une des questions est celle-ci:https://math.stackexchange.com/questions/2765746/inclusion-exclusion-problem-sitting-arrangement , C'était dans un livre de maths-concours grec et je l'ai également trouvé sur ce site.

L'autre question que je n'ai pas trouvée sur Internet, je vais donc la traduire:

Trouvez le nombre de solutions à l'équation $x_1+x_2+x_3=100$, si pour chaque $3\ge i\ge1$, xi est un entier non négatif avec $40\ge x_i$.

J'ai trouvé les solutions à ces deux questions, la raison pour laquelle je les publie également, est de donner une meilleure compréhension au lecteur du message (comme indiqué dans les commentaires), de quel niveau de questions à inclure- le principe d'exclusion me donne des difficultés

Answer 1

La deuxième question, traduite, n'a pas vraiment besoin d'inclusion-exclusion; c'est assez facile à faire en utilisanthttps://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics), qui est une autre technique qui vaut la peine d'être apprise (si vous ne l'avez pas déjà fait):

Écrivons $u_i=40-x_i$, de sorte que la restriction est $u_i\ge0$, puis réécrivez l'équation pour résoudre comme

$$u_1+u_2+u_3=20$$

(Cela vient de $100=x_1+x_2+x_3=(40-u_1)+(40-u_2)+(40-u_3)=120-(u_1+u_2+u_3)$, puis déplacer des éléments.) Les étoiles et les barres indiquent maintenant le nombre de triplets non négatifs additionnés à $20$ est

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

Pour être honnête, je pense que j'aurais du mal à résoudre ce problème en utilisant l'inclusion-exclusion; Je serais intéressé moi-même à voir s'il existe un moyen facile de le faire.

Answer 2

Voici l'approche d'inclusion-exclusion pour le deuxième problème, où $k$ est le nombre de $i\in\{1,2,3\}$ avec $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} Le$$\binom{100-41k+3-1}{3-1}$$ une partie provient d'un nombre d'étoiles et de barres des solutions entières non négatives à $x_1+x_2+x_3=100$ avec $x_i \ge 41$ pour $k$ spécifié $i\in\{1,2,3\}$, de manière équivalente, les solutions entières non négatives à $y_1+y_2+y_3=100-41k$.