Un peu de combinatoire : les inégalités de Bonferroni

Dans le monde merveilleux de la combinatoire, la formule donnant le cardinal de l’union de plusieurs ensembles finis est un grand classique.

Il est un peu moins connu qu’en ne conservant que les premiers termes de la formule en question, on obtient des inégalités, connues sous le nom d’inégalités de Bonferroni.

Cet article en donne une présentation détaillée et se termine par la résolution d’un problème de combinatoire, tiré des Olympiades Internationales de Mathématiques (1989, problème 6).

1 – Le principe d’inclusion / exclusion

Dans ce qui suit, on note $\#X$ le cardinal d’un ensemble fini $X$ .

Il est connu que si $A_{1}$ et $A_{2}$ sont deux ensembles finis, alors :

$\boxed{\#\left(A_{1}\cup A_{2}\right)=\#A_{1}+\#A_{2}-\#\left(A_{1}\cap A_{2}\right)}$

On comprend cette formule en considérant que l’expression $\#A_{1}+\#A_{2}$ fournit une « sur-évaluation » de $\#\left(A_{1}\cup A_{2}\right),$ dans la mesure où les éléments de l’intersection sont tous comptés deux fois. On rectifie donc le tir en retranchant $\#\left(A_{1}\cap A_{2}\right).$

De la même manière, si $A_{1}$ , $A_{2}$ et $A_{3}$ sont trois ensembles finis, l’expression $\#A_{1}+\#A_{2}+\#A_{3}$ donne un majorant de $\#\left(A_{1}\cup A_{2}\cup A_{3}\right)$ puisque certains éléments sont comptés deux fois (ceux qui appartiennent à deux des $A_{i}$ mais pas aux trois) voire trois fois (ceux qui appartiennent aux trois), d’où la formule :

$\begin{multline*}\#\left(A_{1}\cup A_{2}\cup A_{3}\right)=\#A_{1}+\#A_{2}+\#A_{3}-\\\left[\#\left(A_{1}\cap A_{2}\right)+\#\left(A_{1}\cap A_{3}\right)+\#\left(A_{2}\cap A_{3}\right)\right]+\#\left(A_{1}\cap A_{2}\cap A_{3}\right)\end{multline*}$

A présent, passons au cas général …

Théorème 1 (« formule du crible » ou « de Poincaré » ou « principe d’inclusion-exclusion »)

Etant donnés $n$ ensembles finis $A_{1},\cdots,A_{n}$ , si l’on note pour tout $k\in\llbracket1,n\rrbracket$ :

$S_{k}=\sum_{1\leqslant i_{1}<\cdots<i_{k}\leqslant n}\#\left(A_{i_{1}}\cap\cdots\cap A_{i_{k}}\right)$

alors :

$\boxed{\#\bigcup_{i=1}^{n}A_{i}=\sum_{k=1}^{n}\left(-1\right)^{k-1}S_{k}}\qquad\left(\star\right)$

Remarque 1

Si par exemple $n=4$ , alors :

$S_{1}=\#A_{1}\,+\,\#A_{2}\,+\,\#A_{3}\,+\,\#A_{4}$

$\begin{eqnarray*}S_{2} & = & \#\left(A_{1}\cap A_{2}\right)\,+\,\#\left(A_{1}\cap A_{3}\right)\,+\,\#\left(A_{1}\cap A_{4}\right)\\& + & \#\left(A_{2}\cap A_{3}\right)\,+\,\#\left(A_{2}\cap A_{4}\right)\,+\,\#\left(A_{3}\cap A_{4}\right)\end{eqnarray*}$

$\begin{eqnarray*}S_{3} & = & \#\left(A_{1}\cap A_{2}\cap A_{3}\right)\,+\,\#\left(A_{1}\cap A_{2}\cap A_{4}\right)\\& + & \#\left(A_{1}\cap A_{3}\cap A_{4}\right)\,+\,\#\left(A_{2}\cap A_{3}\cap A_{4}\right)\end{eqnarray*}$

$S_{4}=\#\left(A_{1}\cap A_{2}\cap A_{3}\cap A_{4}\right)$

et, avec ces notations :

$\boxed{\#\left(A_{1}\cup A_{2}\cup A_{3}\cap A_{4}\right)=S_{1}-S_{2}+S_{3}-S_{4}}$

Remarque 2

Revenons à n quelconque.

L’entier $S_{k}$ est la somme des cardinaux des intersections $k$ à $k$ des $A_{i}.$ En particulier :

$S_{1}=\sum_{i=1}^{n}\#A_{i}\qquad\text{et}\qquad S_{n}=\#\bigcap_{i=1}^{n}A_{i}$

Noter que la somme qui définit $S_{k}$ comporte $\displaystyle{\binom{n}{k}}$ termes.

Pour une preuve de la formule du crible, voir plus bas : le corollaire qui suit la preuve du Lemme 3.

2 – Des égalités tronquées qui deviennent inégalités

On va maintenant prouver que si, dans l’égalité $\left(\star\right)$ , le second membre est « tronqué », c’est-à-dire si l’on n’en conserve que les $j$ premiers termes (pour un certain $j\in\llbracket1,n-1\rrbracket$ ), alors on obtient une inégalité. Plus précisément :

Théorème 2 (inégalités de Bonferroni)

Si $A_{1},\cdots,A_{n}$ sont des ensembles finis, alors :

$\forall j\in\llbracket1,n\rrbracket,\:\left\{ \begin{matrix}{\displaystyle \#\bigcup_{i=1}^{n}A_{i}\geqslant\sum_{k=1}^{j}\left(-1\right)^{k-1}S_{k}} & & \text{si }j\text{ est pair}\\\\{\displaystyle \#\bigcup_{i=1}^{n}A_{i}\leqslant\sum_{k=1}^{j}\left(-1\right)^{k-1}S_{k}} & & \text{si }j\text{ est impair}\end{matrix}\right.$

Ces inégalités peuvent être formulées en termes de probabilités.
C’est ainsi que le mathématicien italien Carlo Emilio BONFERRONI (1892 – 1960) les publia en 1935, sous une forme appliquée à un problème d’assurance-vie (!), puis en 1936 dans un style plus abstrait.

Le cas particulier $j=1$ est très classique :

Théorème 3 (inégalité de Boole)

Si $A_{1},\cdots,A_{n}$ sont des ensembles finis, alors :

$\#\bigcup_{i=1}^{n}A_{i}\leqslant\sum_{i=1}^{n}\#A_{i}$

Preuve (cliquer pour déplier / replier)

On prouve aisément ceci par récurrence.

Pour $n=1$ , il n’y a rien à démontrer. Pour $n=2$ , on sait que :

$\#\left(A_{1}\cup A_{2}\right)=\#A_{1}+\#A_{2}-\#\left(A_{1}\cup A_{2}\right)\leqslant\#A_{1}+\#A_{2}$

Supposons maintenant l’inégalité de Boole établie au rang $n$ , pour un certain $n\geqslant2$ , et soient $A_{1},\cdots,A_{n+1}$ des ensembles finis. On constate, grâce au cas $n=2$ , que :

$\#\bigcup_{i=1}^{n+1}A_{i}=\#\left[\left(\bigcup_{i=1}^{n}A_{i}\right)\cup A_{n+1}\right]\leqslant\#\bigcup_{i=1}^{n}A_{i}+\#A_{n+1}$

On conclut avec l’hypothèse de récurrence.

Pour traiter le cas général (théorème 2), on aura besoin de quelques résultats préliminaires, rassemblés dans la section suivante.

3 – Trois lemmes techniques

Lemme 1

Soient $a_{0},\cdots,a_{n}$ des réels positifs (avec $n\geqslant2$ ). On suppose qu’il existe $k$ tel que $\left(a_{i}\right)_{0\leqslant i\leqslant k}$ soit croissante et $\left(a_{i}\right)_{k\leqslant i\leqslant n}$ soit décroissante. Si de plus :

$\sum_{i=0}^{n}\left(-1\right)^{i}a_{i}=0$

alors, pour tout $j\in\llbracket0,n-1\rrbracket$ :

$\left\{ \begin{matrix}{\displaystyle \sum_{i=0}^{j}\left(-1\right)^{i}a_{i}\geqslant0} & & \text{si }j\text{ est pair}\\\\{\displaystyle \sum_{i=0}^{j}\left(-1\right)^{i}a_{i}\leqslant0} & & \text{si }j\text{ est impair}\end{matrix}\right.$

Preuve (cliquer pour déplier / replier)

Supposons $j\leqslant k$ .

➡ Si $j$ est pair, alors en posant $j=2q$ :

$\sum_{i=0}^{2q}\left(-1\right)^{i}a_{i}=a_{0}+\sum_{i=1}^{q}\left(a_{2i}-a_{2i-1}\right)\geqslant0$

➡ Si $j$ est impair, alors en posant $j=2q+1$ :

$\sum_{i=0}^{2q+1}\left(-1\right)^{i}a_{i}=\sum_{i=0}^{q}\left(a_{2i}-a_{2i+1}\right)\leqslant0$

Supposons maintenant $j>k$ . On constate que :

$\sum_{i=0}^{j}\left(-1\right)^{i}a_{i}=\underbrace{\sum_{i=0}^{n}\left(-1\right)^{i}a_{i}}_{=0}-\sum_{i=j+1}^{n}\left(-1\right)^{i}a_{i}$

et donc, en posant $\ell=n-i$ dans cette dernière somme :

$\sum_{i=0}^{j}\left(-1\right)^{i}a_{i}=-\sum_{\ell=0}^{n-j-1}\left(-1\right)^{n-\ell}a_{n-\ell}=\left(-1\right)^{n-1}\sum_{\ell=0}^{n-j-1}\left(-1\right)^{\ell}a_{n-\ell}$

ce qui nous ramène au premier cas !

La dernière somme est du signe de $\left(-1\right)^{n-j-1}$ , donc $\sum_{i=0}^{j}\left(-1\right)^{i}a_{i}$ est du signe de $\left(-1\right)^{j}$ .

Corollaire (Application du Lemme 1 aux coefficients binomiaux)

Pour $n\geqslant2$ donné, la suite finie de terme général $\binom{n}{i}$ (pour $0\leqslant i\leqslant n$ ) est d’abord croissante, jusqu’au terme d’indice $\left\lfloor \frac{n+1}{2}\right\rfloor$ , puis décroissante.

De plus :

$\sum_{i=0}^{n}\left(-1\right)^{i}\binom{n}{i}=\left(1-1\right)^{n}=0$

Donc, en appliquant le lemme précédent :

$\forall j\in\llbracket0,n-1\rrbracket,\:\left(-1\right)^{j}\sum_{i=0}^{j}\left(-1\right)^{i}\binom{n}{i}\geqslant0$

Ce résultat peut toutefois être obtenu directement car :

$\forall j\in\llbracket0,n-1\rrbracket,\:\sum_{i=0}^{j}\left(-1\right)^{i}\binom{n}{i}=\left(-1\right)^{j}\binom{n-1}{j}$

Je vous laisse le plaisir 🙂 de mettre au point une preuve de ce dernier résultat, si vous ne le connaissiez pas déjà (ce n’est pas bien difficile, mais si nécessaire vous trouverez tous les détails en consultant l’exercice n° 4 de cette fiche).

Lemme 2

Soient $A_{1},\cdots,A_{n}$ des ensembles finis et $X=\bigcup_{i=1}^{n}A_{i}.$ Pour tout $x\in X$ , on note :

$\theta\left(x\right)=\#\left\{j\in\llbracket1,n\rrbracket;\thinspace x\in A{j}\right\}$

Par ailleurs, si $B\subset X$ , on note :

$\mathds{1}_{B}} \text{ la fonction indicatrice de }B$

Alors, pour tout $k\in\llbracket1,n\rrbracket$ et pour tout $x\in X$ :

$\sum_{1\leqslant i_{1}<\cdots<i_{k}\leqslant n}\mathds{1}_{A_{i_{1}}\cap\cdots\cap A_{i_{k}}}\left(x\right)=\binom{\theta\left(x\right)}{k}$

Preuve (cliquer pour déplier / replier)

En notant $I=\left\{ j\in\llbracket1,n\rrbracket;\thinspace x\in A_{j}\right\}$ , on voit que :

$\mathds{1}_{A_{i_{1}}\cap\cdots\cap A_{i_{k}}}\left(x\right)=1\Leftrightarrow\left\{ i_{1},\cdots,i_{k}\right\} \in\mathcal{P}_{k}\left(I\right)$

où ${\mathcal{P}}_k\left(I\right)$ désigne l’ensemble des parties de $I$ ayant pour cardinal $k$ . Donc :

$\sum_{1\leqslant i_{1}<\cdots<i_{k}\leqslant n}\mathds{1}_{A_{i_{1}}\cap\cdots\cap A_{i_{k}}}\left(x\right)=\# {\mathcal{P}}_k\left(I\right)=\binom{\#I}{k}$

et le résultat en découle puisque $\#I=\theta\left(x\right)$ .

Lemme 3

Soient $A_{1},\cdots,A_{n}$ des ensembles $\left(n\geqslant2\right)$ et $\Omega$ un ensemble contenant chacun des $A_{i}$ .

Alors, la fonction indicatrice de l’union des $A_i$ est donnée par :

$\begin{eqnarray*}\mathds{1}_{A_{1}\cup\cdots\cup A_{n}} & = & \sum_{i=1}^{n}\mathds{1}_{A_{i}}-\sum_{1\leqslant i_{1}<i_2\leqslant n}\mathds{1}_{A_{i_{1}}\cap A_{i_{2}}}+\cdots\\& + & \left(-1\right)^{k-1}\sum_{1\leqslant i_{1}<\cdots<i_k\leqslant n}\mathds{1}_{A_{i_{1}}\cap\cdots\cap A_{i_{k}}}+\cdots\\& + & \left(-1\right)^{n-1}\mathds{1}_{A_{1}\cap\cdots\cap A_{n}}\end{eqnarray*}$

Preuve (cliquer pour déplier / replier)

Pour tout $x\in\Omega$ :

$\begin{eqnarray*}1-\prod_{i=1}^{n}\left(1-\mathds{1}_{A_{i}}\left(x\right)\right)=1 & \Leftrightarrow & \exists i\in\llbracket1,n\rrbracket;\thinspace1-\mathds{1}_{A_{i}}\left(x\right)=0\\& \Leftrightarrow & \exists i\in\llbracket1,n\rrbracket;\thinspace x\in A_{i}\end{eqnarray*}$

donc :

$1-\prod_{i=1}^{n}\left(1-\mathds{1}_{A_{i}}\left(x\right)\right)=\mathds{1}_{A_{1}\cup\cdots\cup A_{n}}\left(x\right)\qquad\left(\star\star\right)$

Par ailleurs, on connaît la formule de développement d’un polynôme unitaire scindé (ici, à coefficients entiers, mais plus généralement à coefficients dans un anneau commutatif) :

$\begin{eqnarray*}\prod_{i=1}^{n}\left(X-a_{i}\right) & = & X^{n}-\left(\sum_{i=1}^{n}a_{i}\right)X^{n-1}\\& & +\left(\sum_{1\leqslant i_{1}<i_{2}\leqslant n}a_{i_{1}}a_{i_{2}}\right)X^{n-2}-\cdots\\& & \cdots+\left(-1\right)^{n}\prod_{i=1}^{n}a_{i}\end{eqnarray*}$

En remplaçant, pour chaque $i\in\llbracket1,n\rrbracket$ , le coefficient $a_{i}$ par $\mathds{1}_{A_{i}}\left(x\right)$ et en évaluant l’identité polynomiale en 1, on obtient :

$\begin{eqnarray*}1-\prod_{i=1}^{n}\left(1-\mathds{1}_{A_{i}}\left(x\right)\right) & = & \sum_{i=1}^{n}\mathds{1}_{A_{i}}\left(x\right)-\sum_{1\leqslant i_{1}<i_{2}\leqslant n}\mathds{1}_{A_{i_{1}}}\left(x\right)\mathds{1}_{A_{i_{2}}}\left(x\right)+\cdots\\& &\cdots+\left(-1\right)^{k-1}\sum_{1\leqslant i_{1}<\cdots<i_{k}\leqslant n}\mathds{1}_{A_{i_{1}}}\left(x\right)\cdots\mathds{1}_{A_{i_{k}}}\left(x\right)+\cdots\\& &\cdots+\left(-1\right)^{n-1}\prod_{i=1}^{n}\mathds{1}_{A_{i}}\left(x\right)\end{eqnarray*}$

d’où le résultat, d’après $\left(\star\star\right)$ .

Corollaire

En passant aux cardinaux dans l’égalité établie au lemme 3 (ce qui suppose bien sûr que les ensembles en présence soient tous finis) on obtient la formule du crible.

4 – Où l’on assemble les pièces du puzzle

Nous prouvons maintenant le théorème 2. Pour cela, reprenons les notations du théorème 1 et posons, pour tout $j\in\llbracket1,n-1\rrbracket$ :

$a_{j}=\#\bigcup_{i=1}^{n}A_{i}-\left[\sum_{k=1}^{j}\left(-1\right)^{k-1}S_{k}\right]$

D’après le lemme 2, en notant toujours $X=\bigcup_{i=1}^{n}A_{i}$ et en intervertissant deux sommes :

$a_{j}=\sum_{x\in X}\left[1-\sum_{k=1}^{j}\left(-1\right)^{k-1}\binom{\theta\left(x\right)}{k}\right]$

c’est-à-dire :

$a_{j}=\sum_{x\in X}\left[\sum_{k=0}^{j}\left(-1\right)^{k}\binom{\theta\left(x\right)}{k}\right]$

Enfin, d’après le lemme 1 et son corollaire, chacune des sommes internes est du signe de $\left(-1\right)^{j}$ , et par conséquent $a_{j}$ aussi.

5 – Une jolie application d’une inégalité de Bonferroni

Les 30-èmes OIM (Olympiades Internationales de Mathématiques) se sont tenues en Allemagne en 1989. Le 6-ème problème proposé était le suivant :

Une permutation $\left(x_{1},x_{2},\cdots,x_{2n}\right)$ de l’ensemble $\llbracket1,2n\rrbracket$ , où $n\in\mathbb{N}^\star$ , possède la propriété $P$ s’il existe au moins un indice $i\in\left\{1,2,\cdots,2n-1\right\}$ tel que $\left|x_{i}-x_{i+1}\right|=n.$

Prouver que, pour tout $n,$ le nombre de permutations possédant la propriété $P$ est supérieur au nombre de celles qui ne la possèdent pas.

Dans ce contexte, si $p\in\mathbb{N}^{\star}$ , on appelle « permutation de l’ensemble $\llbracket1,p\rrbracket$ » toute liste de longueur $p$ constituée exactement des entiers de $1$ à $p,$ mais dans un ordre quelconque. Il est bien connu qu’il existe $p!$ telles permutations.

Cela dit, notons $A_{i}$ l’ensemble des permutations de l’ensemble $\llbracket1,2n\rrbracket$ , pour lesquelles $i$ et $i+n$ occupent des positions contigües (avec $i\in\llbracket1,n\rrbracket$ ).

Par exemple, pour $n=4$ , les permutations $\left(6,1,7,3,2,5,4,8\right)$ et $\left(2,3,7,1,8,5,6,4\right)$ appartiennent à $A_{3}$ puisque $3$ et $7=3+4$ se retrouvent côte à côte; alors que la permutation $\left(8,2,1,7,6,4,5,3\right)$ n’appartient pas à $A_{3}$ .