Principe d'inclusion-exclusion

Parmi 20 étudiants, 10 étudient les mathématiques, 11 étudient la physique, et 4 étudient les deux. Combien y a-t-il d’étudiants qui n’étudient ni les mathématiques ni la physique ?

La construction d'un diagramme de Venn permet de visualiser simplement la répartition générale des étudiants.

Une zone de couleur représente un groupe. E représente le groupe entier d’étudiants, M représente ceux qui ont la propriété d'« étudier les mathématiques », P représente ceux qui possèdent la propriété d'« étudier la physique ».

On note ensuite pour chaque zone le nombre d’étudiants. Étant donné que quatre personnes étudient à la fois les mathématiques et la physique, l’intersection des deux cercles compte 4 étudiants. Il reste donc 10 – 4 = 6 personnes qui étudient les mathématiques mais pas la physique et 11 – 4 = 7 personnes qui étudient la physique mais pas les mathématiques. Par suite, il reste donc 20 – (6 + 4 + 7) = 3 personnes qui n’étudient ni les mathématiques, ni la physique.

Ce résultat se retrouve facilement en utilisant le principe d’inclusion-exclusion qui donne le nombre d’étudiants ne possédant pas ces deux propriétés : 20 – 10 – 11 + 4 = 3.

Soient A et B deux ensembles finis, la formule s'écrit

${\displaystyle |A\cup B|=|A|+|B|-|A\cap B|}$

où |A| et |B| représentent les cardinaux respectifs de A et B.

En d’autres termes, nous pouvons compter les éléments de la réunion de deux ensembles A et B en additionnant les cardinaux de ces deux ensembles et en soustrayant le cardinal de leur intersection.

Les sommes partielles des premiers termes de la formule fournissent alternativement un majorant et un minorant de la somme complète, et peuvent être utilisées comme approximations de celle-ci : ces majorations et minorations sont appelées les inégalités de Bonferroni, du nom de leur auteur, Carlo Emilio Bonferroni.

En combinatoire, la formule du crible permet de déterminer le nombre de dérangements d'un ensemble fini, et donc de résoudre le problème des rencontres. Un dérangement d'un ensemble X est une bijection de X sur lui-même sans point fixe. Grâce au principe d'inclusion-exclusion, et en prenant pour A_i l'ensemble des permutations de X laissant i invariant, on peut prouver[1] que si le cardinal de X est égal à n, alors le nombre de dérangements de X est égal à ${\displaystyle n!\sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}}$. C'est l'entier le plus proche de n!/e (où e désigne la base des logarithmes népériens). Il s'ensuit que la probabilité pour qu'une bijection prise au hasard[2] soit un dérangement tend rapidement vers 1/e lorsque n tend vers l'infini.

On peut pousser plus loin l'étude statistique des points fixes des permutations. Notons N(ω) le nombre de points fixes d'une permutation ω. Ce nombre est nul si et seulement si ω est un dérangement. En cela, la proposition suivante précise le résultat concernant les dérangements (qui n'est autre que le calcul de ${\displaystyle \mathbb {P} \left(N=0\right)}$) :

Proposition[1] — Pour tout entier k compris entre 0 et n,

${\displaystyle \mathbb {P} (N=k)\ =\ {\frac {1}{k!}}\quad \sum _{\ell =0}^{n-k}{\frac {(-1)^{\ell }}{\ell$ !}}} .

En particulier, la loi de N est très proche de la loi de Poisson de paramètre 1, pour n grand. Cela illustre le paradigme de Poisson, selon lequel une somme d'un grand nombre de variables de Bernoulli de petit paramètre, peu corrélées, suit approximativement la loi de Poisson : N peut être vue comme une telle somme. Cette écriture permet de calculer l'espérance et la variance de N plus rapidement qu'à partir de l'expression ci-dessus de la loi de N.

Le principe d'inclusion-exclusion permet aussi de montrer[3], en prenant pour A_τ l'ensemble des permutations de X admettant un cycle τ d'ordre 2, que le nombre de permutations n'ayant pas de cycle d'ordre 2 est ${\displaystyle n!\sum _{k=0}^{m}{\frac {(-1)^{k}}{2^{k}k!}}}$, où m est la partie entière de n/2. Plus généralement, le nombre de permutations n'ayant pas de cycle d'ordre p est ${\displaystyle n!\sum _{k=0}^{m}{\frac {(-1)^{k}}{p^{k}k!}}}$, où m est la partie entière de n/p.

Soient X et Y deux ensembles finis. Considérons l'ensemble ${\displaystyle E:=Y^{X}}$ des applications de X dans Y et, pour tout élément y de Y, le sous-ensemble ${\displaystyle A_{y}}$ des applications qui ne prennent jamais la valeur y. L'ensemble des surjections de X dans Y est alors égal à ${\displaystyle E\setminus \bigcup _{y\in Y}A_{y}}$ et son cardinal vaut donc :

${\displaystyle {\begin{aligned}S_{p,q}&=|E|+\sum _{k=1}^{q}(-1)^{k}\sum _{Z\subset Y \atop |Z|=k}\left|\bigcap _{y\in Z}A_{y}\right|\\&=\sum _{k=0}^{q}(-1)^{k}\sum _{Z\subset Y \atop |Z|=k}\left|(Y\setminus Z)^{X}\right|\\&=\sum _{k=0}^{q}(-1)^{k}\sum _{Z\subset Y \atop |Z|=k}(q-k)^{p}\\&=\sum _{k=0}^{q}(-1)^{k}{\binom {q}{k}}(q-k)^{p}\end{aligned}}}$

ou encore, par changement d'indice :

Proposition[1] — Soient ${\displaystyle p,q\in \mathbb {N} }$. Le nombre ${\displaystyle S_{p,q}}$ de surjections d'un ensemble à ${\displaystyle p}$ éléments dans un ensemble à ${\displaystyle q}$ éléments est donné par :

${\displaystyle S_{p,q}=\sum _{j=0}^{q}(-1)^{q-j}{\binom {q}{j}}j^{p}}$.

Soit m et n deux entiers strictement positifs. Le nombre de Wortpitzky[4] ${\displaystyle W_{mn}}$ est le nombre de façon de colorier m carrés disposés en ligne avec n couleurs, chaque couleur apparaissant au moins une fois, et chaque carré pouvant aussi rester incolore. On peut trouver une expression de ${\displaystyle W_{mn}}$ en utilisant la version probabiliste du principe d'inclusion-exclusion. Pour chaque carré, on tire une couleur au hasard parmi {1, ..., n+1} avec une loi uniforme. Si la couleur tirée est n+1, cela signifie que le carré est incolore. Pour chaque couleur i variant de 1 à n, on note ${\displaystyle A_{i}}$ l'événement : la couleur i n'est utilisée dans aucun carré. On a alors :

${\displaystyle \mathbb {P} (A_{i})={\frac {n^{m}}{(n+1)^{m}}}}$

${\displaystyle \mathbb {P} (A_{i}\cup A_{j})={\frac {(n-1)^{m}}{(n+1)^{m}}}}$ pour tout i < j.

${\displaystyle \mathbb {P} (A_{i}\cup A_{j}\cup A_{k})={\frac {(n-2)^{m}}{(n+1)^{m}}}}$ pour tout i < j < k

etc. La formule d'inclusion-exclusion donne :

${\displaystyle \mathbb {P} \left(\,\bigcup _{i=1}^{n}A_{i}\,\right)=\sum _{k=1}^{n}(-1)^{k-1}{n \choose k}{\frac {(n+1-k)^{m}}{(n+1)^{m}}}}$

La probabilité de l'événement contraire n'est autre que ${\displaystyle {\frac {W_{mn}}{(n+1)^{m}}}}$, d'où, finalement :

${\displaystyle W_{mn}=\sum _{k=0}^{n}(-1)^{k}{n \choose k}(n+1-k)^{m}}$