1.4 Soustraction: Le principe d’inclusion-exclusion

Le principe de la somme est particulièrement utile, mais aussi très restrictif. En effet, beaucoup de problèmes de combinatoire nécessitent de compter le nombre d’éléments de l’union de deux ensembles, mais dans la plupart des cas, il est absurde de faire l’hypothèse que l’intersection est vide. Le principe d’inclusion-exclusion vient remédier à ce problème. Pour le moment, nous énonçons le principe seulement dans le cas de deux ensembles, mais sachez que nous aurons l’occasion, plus tard dans le cours, de le généraliser à un nombre arbitraire d’ensembles, ce qui en fera un outil particulièrement puissant. Bien que nous ne le traiterons pas dans ce cours, sachez que dans le cours de combinatoire 2, une généralisation supplémentaire du principe d’inclusion-exclusion sera faite. L’idée est en fait de réaliser que le principe d’inclusion-exclusion est un cas particulier de la théorie des relations d’ordre partiel.

Le principe d’inclusion-exclusion nous affirme essentiellement que si une tâche peut être complétée soit de $\displaystyle n_{1}$ façons ou de $\displaystyle n_{2}$ façons, et qu’il y a $\displaystyle n_{3}$ de ces méthodes qui sont en commun, alors il y a $\displaystyle n_{1}+n_{2}-n_{3}$ façons de compléter la tâche. Il s’agit cependant de l’énoncé en termes de la théorie des ensembles qui sera le plus intéressant pour nous.

Théorème 1.4.1:

Principe d’inclusion-exclusion. Si $\displaystyle A$ et $\displaystyle B$ sont des ensembles, alors la cardinalité de l’union est la somme de la cardinalité de chacun des deux ensembles, moins la cardinalité de l’union. C’est à dire:

\displaystyle|A\cup B|=|A|+|B|-|A\cap B|

Démonstration.

La démonstration du principe d’inclusion-exclusion repose sur l’idée suivante:

\displaystyle A=(A\backslash B)\cup(A\cap B)

\displaystyle B=(B\backslash A)\cup(A\cap B)

Comme les ensembles $\displaystyle A\backslash B$ , $\displaystyle B\backslash A$ et $\displaystyle A\cap B$ sont disjoints, le principe de la somme nous permet donc d’affirmer:

\displaystyle|A\cup B|=|A\backslash B|+|B\backslash A|+|A\cap B|=\Big{(}|A% \backslash B|+|A\cap B|\Big{)}+\Big{(}|B\backslash A|+|A\cap B|\Big{)}-|A\cap B% |=|A|+|B|-|A\cap B|

∎

Exemple 1.4.1.

Combien y a-t-il de mots de 5 lettres commençant par $\displaystyle A$ ou se terminant par $\displaystyle ZZ$ ? Notez qu’ici un mot fait référence à un agencement de lettres quelconques et pas nécessairement un mot que l’on peut trouver dans un dictionnaire français ou anglais. Par exemple, $\displaystyle ABCZZ$ serait un mot acceptable. Ici, le OU nous fait penser qu’il s’agit du principe de la somme. Mais en portant une attention particulière au problème, on réalise que ce n’est pas le cas, car il y a plusieurs mots qui commencent par $\displaystyle A$ et se terminent par $\displaystyle ZZ$ . Il s’agit donc d’une application du principe d’inclusion-exclusion. Le nombre de possibilités sera donc donné par:

(Nombre de mots commençant par A) + (Nombre de mots terminant par ZZ) - (Nombre de mots commençant par A et terminant par ZZ)

Maintenant, pour calculer chacune de ces composantes, on remarque qu’il s’agit d’une application du principe du produit. Pour le nombre de mots commençant par $\displaystyle A$ , on a donc:

\displaystyle 1\times 26\times 26\times 26\times 26=26^{4}=456\leavevmode% \nobreak\ 976\leavevmode\nobreak\ \textrm{possibilit\'{e}s}

Pour le nombre de mots se terminant par $\displaystyle ZZ$ , on a:

\displaystyle 26\times 26\times 26\times 1\times 1=26^{3}=17\leavevmode% \nobreak\ 576\leavevmode\nobreak\ \textrm{possibilit\'{e}s}

Puis, le nombre de mots commençant par $\displaystyle A$ et se terminant par $\displaystyle ZZ$ est donné par:

\displaystyle 1\times 26\times 26\times 1\times 1=26^{2}=676\leavevmode% \nobreak\ \textrm{possibilit\'{e}s}

Le principe d’inclusion-exclusion nous affirme donc que le nombre de mots commençant par $\displaystyle A$ ou se terminant par $\displaystyle ZZ$ est donné par:

\displaystyle 26^{4}+26^{3}-26^{2}=456976+17576-676=473\leavevmode\nobreak\ 87% 6\leavevmode\nobreak\ \textrm{possibilit\'{e}s}

Le principe d’inclusion-exclusion peut, bien entendu, être généralisé à plusieurs ensembles. C’est ce que nous allons énoncer immédiatement dans le théorème suivant.

Théorème 1.4.2:

Principe d’inclusion-exclusion version générale. Si $\displaystyle A,B$ et $\displaystyle C$ sont trois ensembles, alors la cardinalité de leur union est donné par l’expression suivante:

\displaystyle|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B% \cap C|

Plus généralement, si on a une collection de $\displaystyle n$ ensembles, disons $\displaystyle A_{1},A_{2},...,A_{n}$ , alors la cardinalité de leur union est donné par l’expression suivante:

\displaystyle\left|\bigcup_{i=1}^{n}A_{i}\right|=\sum_{B\subseteq[n]}\left((-1% )^{|B|+1}\left|\bigcap_{i\in B}A_{i}\right|\right)

où $\displaystyle[n]$ est une notation pour représenter l’ensemble $\displaystyle\{1,2,...,n\}$ .

Dans le théorème, il faut interpréter une intersection d’aucun ensemble comme étant vide, et donc sa cardinalité est interprétée comme étant $\displaystyle 0$ . Sous cette forme, le principe d’inclusion-exclusion peut être utilisé pour compter le nombre d’éléments satisfaisant à au moins une des propriétés données. En pratique, c’est beaucoup plus souvent le contraire qui nous intéresse: Compter le nombre d’éléments qui ne satisfont aucune des propriétés énoncées. Dans ce cas, il faut travailler avec le complément. Pour ce faire, il faut considérer un ensemble universel $\displaystyle E$ . Cet ensemble est interprété comme étant l’ensemble de toutes les possibilités. Par la loi de De Morgan, nous avons:

\displaystyle\left|\bigcap_{i=1}^{n}A_{i}^{c}\right|=\left|\left(\bigcup_{i=1}% ^{n}A_{i}\right)^{c}\right|=|E|-\left|\bigcup_{i=1}^{n}A_{i}\right|

En remplaçant dans notre expression pour le principe d’inclusion-exclusion, on obtient donc:

\displaystyle\left|\bigcap_{i=1}^{n}A_{i}^{c}\right|=|E|-\sum_{B\subseteq[n]}% \left((-1)^{|B|+1}\left|\bigcap_{i\in B}A_{i}\right|\right)=|E|+\sum_{B% \subseteq[n]}\left((-1)^{|B|}\left|\bigcap_{i\in B}A_{i}\right|\right)

Exemple 1.4.2.

Combien y a-t-il de mots de $\displaystyle 5$ lettres qui contiennent au moins un $\displaystyle A$ et un $\displaystyle B$ et un $\displaystyle C$ ? Pour répondre à cette question, il est plus facile de travailler avec le complément. Nous allons donc définir les quatre ensembles suivants:

$\displaystyle E$ :	L’ensemble de tous les mots de $\displaystyle 5$ lettres.
$\displaystyle E_{A}$ :	L’ensemble des mots de $\displaystyle 5$ lettre qui ne contiennent pas de $\displaystyle A$ .
$\displaystyle E_{B}$ :	L’ensemble des mots de $\displaystyle 5$ lettre qui ne contiennent pas de $\displaystyle B$ .
$\displaystyle E_{C}$ :	L’ensemble des mots de $\displaystyle 5$ lettre qui ne contiennent pas de $\displaystyle C$ .

La cardinalité de chacun de ces ensembles, ainsi que la cardinalité de leur intersection, est particulièrement facile à calculer à l’aide du principe du produit. Maintenant, remarquons que ce que l’on cherche est en fait la cardinalité de l’ensemble $\displaystyle E_{A}^{c}\cap E_{B}^{c}\cap E_{C}^{c}$ . Par le principe d’inclusion-exclusion, on a donc:

$\displaystyle\displaystyle\|E_{A}^{c}\cap E_{B}^{c}\cap E_{C}^{c}\|$	$\displaystyle\displaystyle=$	$\displaystyle\displaystyle\|E\|-\|E_{A}\|-\|E_{B}\|-\|E_{C}\|+\|E_{A}\cap E_{B}\|+\|E_{A}% \cap E_{C}\|+\|E_{B}\cap E_{C}\|-\|E_{A}\cap E_{B}\cap E_{C}\|$
	$\displaystyle\displaystyle=$	$\displaystyle\displaystyle 26^{5}-25^{5}-25^{5}-25^{5}+24^{5}+24^{5}+24^{5}-23% ^{5}$
	$\displaystyle\displaystyle=$	$\displaystyle\displaystyle 26^{5}-3\left(25^{5}\right)+3\left(24^{5}\right)-23% ^{5}$
	$\displaystyle\displaystyle=$	$\displaystyle\displaystyle 36030$