Théorie > Combinatoire > Dénombrement (suite)


Général

Introduction Chapitre entier

Points théoriques

Comptage direct Bijection Inclusion-exclusion Récurrence

Exercices

Exercice 1 Exercice 2 Exercice 3 Exercice 4 Exercice 5 Exercice 6

Inclusion-exclusion

Le principe d'inclusion-exclusion est une formule permettant de calculer le nombre d'éléments dans une union d'ensembles à partir du nombre d'éléments dans leurs différentes intersections. L'exemple le plus simple consiste en deux ensembles $A$ et $B$. S'ils sont disjoints (ils n'ont aucun élément en commun), alors on a bien sûr $|A \cup B| = |A| + |B|$. Par contre, s'ils ont des éléments communs, alors en calculant cette somme $|A|+|B|$, on compte deux fois les éléments qui sont dans $A \cap B$ (c'est-à-dire dans $A$ et $B$ à la fois). Il faut donc retirer le nombre d'éléments communs aux deux ensembles, et on a la formule générale
$$|A \cup B| = |A| + |B| - |A \cap B|.$$


On peut faire le meme raisonnement pour trois ensembles $A$, $B$ et $C$. On commence par calculer la somme $|A| + |B| + |C|$, mais encore une fois on a compté plus d'une fois les éléments se situant dans deux ensembles à la fois. On retranche donc $|A \cap B| + |B \cap C| + |C \cap A|$ du résultat. Mais si maintenant, on considère les éléments se situant dans les trois ensembles à la fois, alors on les a compté trois fois chacun lors de la première somme avant de les retrancher trois fois : on n'a donc au final pas compté ces éléments! Il faut donc à nouveau compter les éléments de $A \cap B \cap C$, ce qui donne la formule
$$|A \cup B \cup C| = |A| + |B| + |C| - |A\cap B| - |B \cap C| - |C \cap A| + |A \cap B \cap C|.$$ On comprend mieux le terme inclusion-exclusion, puisqu'on ajoute certains termes avant d'en retrancher d'autres, puis d'en rajouter à nouveau.



Ce raisonnement se généralise en fait à $n$ ensembles :

Soient $A_1, \ldots, A_n$ des ensembles. On a
$$|A_1 \cup \ldots \cup A_n| = \sum_{k=1}^n \left( (-1)^{k-1} \sum_{1\leq i_1 < \ \ldots \ < i_k \leq n} |A_{i_1} \cap \ldots \cap A_{i_k}| \right).$$

Cette formule peut sembler compliquée mais elle ne fait que généraliser les formules que nous avons vues pour $n = 2$ et $n= 3$. En effet, pour $k = 1$ on retrouve tous les ensembles seuls, pour $k = 2$, on a $(-1)^{2-1} = -1$ et on retire donc les cardinaux de toutes les intersections deux par deux, puis pour $k = 3$ on rajoute les intersections trois par trois, et ainsi de suite jusqu'à l'intersection de tous les ensembles.

Application en combinatoire

Un exemple assez connu où le principe d'inclusion-exclusion est le suivant :

Exemple : Combien y a-t-il de nombres compris entre $1$ et $1000$ divisibles par $2$, par $3$ ou par $5$?

L'erreur type est de se dire "Il y a $500$ nombres pairs, $333$ nombres divisibles par $3$ et $200$ nombres divisibles par $5$, donc la réponse est $500+333+200=1033$." Evidemment, on constate immédiatement que le raisonnement est erroné puisqu'on obtient une réponse supérieure à $1000$. Le problème est que nous avons compté plusieurs fois les nombres multiples de $6$, de $10$ ou de $15$ : il s'agit exactement du problème de l'inclusion exclusion. La bonne attitude est donc de noter $A$ l'ensemble des nombres (entre $1$ et $1000$) pairs, $B$ l'ensemble des nombres multiples de $3$ et $C$ l'ensemble des nombres multiples de $5$. Nous cherchons alors le cardinal de $A \cup B \cup C$, et le principe d'inclusion-exclusion s'applique :
$$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |B \cap C| - |C \cap A| + |A \cap B \cap C|.$$ Or, on a $|A| = 500$, $|B| = 333$, $|C| = 200$, $|A \cap B| = 166$ (car $A \cap B$ est l'ensemble des nombres multiples de $6$), $|B \cap C| = 66$, $|C \cap A| = 100$ et $|A \cap B \cap C| = 33$, d'où au final
$$|A \cup B \cup C| = 500+333+200-166-66-100+33=\boxed{734}.$$
Il existe aussi des exemples du même type que ceux que nous avons rencontrés jusqu'à présent, comme le suivant.

Exemple : Je possède $8$ photos différentes de mes vacances, et je désire les distribuer à mes $5$ amis. Pour que tout le monde soit content, chaque ami doit recevoir au moins une photo. De combien de manière puis-je effectuer ma distribution?

S'il n'y avait pas la condition comme quoi chaque ami doit recevoir au moins une photo, on pourrait simplement considérer les photos une à une et décider pour chacune à qui on la donne : on aurait donc $5^8$ possibilités. En fait, on peut le voir comme un arrangement avec répétitions de $8$ objets parmi $5$. Le minimum d'une photo par personne nous empêche cependant de procéder de la sorte, et il n'est pas évident de voir comment on pourrait effectuer un comptage direct. Une idée déjà suggérée dans ce chapitre est alors de passer au complémentaire, c'est-à-dire de compter le nombre de façons de distribuer les photos de sorte qu'au moins un ami ne recoive aucune photo. Cela nous fait penser au principe d'inclusion exclusion, puisqu'en notant
$$A_i = \{\text{distributions où l'ami numéro $i$ ne reçoit pas de photo}\},$$ on cherche le cardinal de $A_1 \cup \ldots \cup A_5$. Pour que le principe d'inclusion-exclusion soit utile, il faut qu'il soit facile d'évaluer le cardinal d'une intersection de $A_i$. Mais cela est effectivement aisé! En effet, le cardinal d'une intersection $A_{i_1} \cap \ldots \cap A_{i_k}$ (avec $k$ ensembles différents) représente le nombre de façons de distribuer $8$ photos à $5$ amis sans en donner aux amis numéro $i_1, \ldots, i_k$. Cela revient à distribuer $8$ photos à $5-k$ amis, et le cardinal vaut donc $(5-k)^8$. Le principe d'inclusion-exclusion donne donc :
$$\begin{align}
|A_1 \cup \ldots \cup A_5| & = \sum_{k=1}^5 \left( (-1)^{k-1} \sum_{1\leq i_1 < \ \ldots \ < i_k \leq 5} |A_{i_1} \cap \ldots \cap A_{i_k}| \right) \\
& = \sum_{k=1}^5 \left( (-1)^{k-1} \sum_{1\leq i_1 < \ \ldots \ < i_k \leq 5} (5-k)^8 \right)
\end{align}$$ Pour $k$ fixé, les termes de la somme intérieure sont tous identiques (égaux à $(5-k)^8$, et il reste donc juste à évaluer combien il y a de termes dans cette somme. Le nombre de termes est simplement égal au nombre de façons de choisir les indices $i_1, \ldots, i_k$ dans $\{1, \ldots, 5\}$, c'est-à-dire égal à $C^k_5$. On a donc
$$\begin{align}
|A_1 \cup \ldots \cup A_5| & = \sum_{k=1}^5 \left( (-1)^{k-1} \cdot C^k_5 \cdot(5-k)^8 \right) \\[2mm]
&= C^1_5 \cdot 4^8 - C^2_5 \cdot 3^8 + C^3_5 \cdot 2^8 - C^4_5 \cdot 1^8 + C^5_5 \cdot 0^8 \\[2mm]
&= 5\cdot 65536 - 10 \cdot 6561 + 10 \cdot 256 - 5 \cdot 1\\[2mm]
&= 264625
\end{align}$$ La réponse au problème initial est donc $5^8 - 264625 = \boxed{126000}$.