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
  • \mathbb{N}_{n} l’ensemble \left\{ 1,\cdots,n\right\} , pour n\in\mathbb{N}^{\star}

Il est bien 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\mathbb{N}_{n} :

    \[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\mathbb{N}_{n-1}), 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\mathbb{N}_{n-1},\:\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.

George-Boole

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\left\{0,\cdots,n-1\right\} :

    \[\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 toute dernière somme est du signe de \left(-1\right)^{n-j-1} et donc {\displaystyle \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\left\{0,\cdots,n-1\right\} ,\:\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\left\{ 0,\cdots,n-1\right\} ,\:\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 difficile).

Lemme 2

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

    \[\theta\left(x\right)=\#\left\{j\in\mathbb{N}_{n};\thinspace x\in A{j}\right\}\]

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

    \[\mathds{1}_{B}} \text{ la fonction caractéristique de } B\]

Alors, pour tout k\in\mathbb{N}_{n} 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\mathbb{N}_{n};\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)\]


{\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 caractéristique 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\mathbb{N}_{n};\thinspace1-\mathds{1}_{A_{i}}\left(x\right)=0\\& \Leftrightarrow & \exists i\in\mathbb{N}_{n};\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\mathbb{N}_{n}, 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\mathbb{N}_{n-1} :

    \[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 {\displaystyle 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 \left{ 1,2,\cdots,2n\right}, 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.

D’abord un point de vocabulaire : dans ce contexte, si p\in\mathbb{N}^{\star}, on nomme « permutation de l’ensemble \left\{ 1,\cdots,p\right\} » 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 \left\{ 1,2,\cdots,2n\right\} , pour lesquelles i et i+n occupent des positions contigües (avec i\in\left\{ 1,\cdots,n\right\}).

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}.

Mais revenons au cas général…

Le nombre de permutations de \left\{ 1,2,\cdots,2n\right\} possédant la propriété P est :

    \[\varphi_{n}=\#\bigcup_{i=1}^{n}A_{i}\]

Le calcul explicite de \varphi_{n} n’a pas l’air commode, mais en appliquant une inégalité de Bonferroni (théorème 2 avec j=2), on voit que :

    \[\varphi_{n}\geqslant\sum_{i=1}^{n}\#A_{i}-\sum_{1\leqslant i<j\leqslant n}\#\left(A_{i}\cap A_{j}\right)\]

Or d’une part, pour tout i\in\left\{ 1,\cdots,n\right\} :

    \[\#A_{i}=2\left(2n-1\right)\left(2n-2\right)!=2\left(2n-1\right)!\]

et, d’autre part, pour tout \left(i,j\right)\in\left\{ 1,\cdots,n\right\} ^{2} tel que i<j :

    \[ \#\left(A_{i}\cap A_{j}\right)=8\frac{\left(2n-3\right)\left(2n-2\right)}{2}\left(2n-4\right)!=4\left(2n-2\right)! \]

et donc :

    \[ \varphi_{n}\geqslant2n\left(2n-1\right)!-\binom{n}{2}4\left(2n-2\right)!=2n^{2}\left(2n-2\right)!\]

Quant au nombre de permutations ne possédant pas la propriété P, il vaut :

    \[ \psi_{n}=\left(2n\right)!-\varphi_{n} \]

et il s’agit de prouver que \varphi_{n}>\psi_{n}, autrement dit que 2\varphi_{n}-\left(2n\right)!>0.

Or, manifestement :

    \[2\varphi_{n}-\left(2n\right)!\geqslant4n^{2}\left(2n-2\right)!-\left(2n\right)!=2n\left(2n-2\right)!>0\]

Et voilà !


Vos questions ou remarques seront toujours les bienvenues. Vous pouvez laisser un commentaire ci-dessous ou bien passer par le formulaire de contact.

Partager cet article
  • 1
  •  
  •  
  •  

Laisser un commentaire