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

article-prépa-scientifique

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 :

    \[ \#\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}\]

    \[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)\]

    \[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)\]

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

et, avec ces notations :

    \[\#\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 S_{k} comporte \binom{n}{k} termes.

→ Pour une preuve de la formule du crible, voir plus bas, juste après le 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 Carlo Emilio BONFERRONI (1892 – 1960), mathématicien italien, 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 constitue l’inégalité de Boole.

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} \]

 

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 \]

    \[\text{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. 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 \]

Et 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}\qquad\text{et donc, en changeant d'indice }\left(\ell=n-i\right)\text{ :} \]

    \[ \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 d’élaborer (ce n’est pas difficile) une preuve de ce dernier résultat, si vous ne le connaissiez pas déjà 🙂

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 :

    \[ \mathbbm{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}\mathbbm{1}_{A_{i_{1}}\cap\cdots\cap A_{i_{k}}}\left(x\right)=\binom{\theta\left(x\right)}{k} \]

 

En notant I=\left\{ j\in\mathbb{N}_{n};\thinspace x\in A_{j}\right\}, on voit en effet que :

    \[ \mathbbm{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) \]

d’où le résultat puisque, par définition, \#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{multline*} \mathbbm{1}_{A_{1}\cup\cdots\cup A_{n}} = \sum_{i=1}^{n}\mathbbm{1}_{A_{i}}-\sum_{1\leqslant i_{1}<i_{2}\leqslant n}\mathbbm{1}_{A_{i_{1}}\cap A_{i_{2}}}+\cdots\\ +\left(-1\right)^{k-1}\sum_{1\leqslant i_{1}<\cdots<i_{k}\leqslant n}\mathbbm{1}_{A_{i_{1}}\cap\cdots\cap A_{i_{k}}}+\cdots+\left(-1\right)^{n-1}\mathbbm{1}_{A_{1}\cap\cdots\cap A_{n}} \end{multline*}

 

Preuve. Pour tout x\in\Omega :

    \[ 1-\prod_{i=1}^{n}\left(1-\mathbbm{1}_{A_{i}}\left(x\right)\right)=1\Leftrightarrow\exists i\in\mathbb{N}_{n};\thinspace1-\mathbbm{1}_{A_{i}}\left(x\right)=0\Leftrightarrow\exists i\in\mathbb{N}_{n};\thinspace x\in A_{i} \]

donc :

    \[ 1-\prod_{i=1}^{n}\left(1-\mathbbm{1}_{A_{i}}\left(x\right)\right)=\mathbbm{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) :

    \[ \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+\left(-1\right)^{n}\prod_{i=1}^{n}a_{i} \]

En remplaçant, pour chaque i\in\mathbb{N}_{n}, a_{i} par \mathbbm{1}_{A_{i}}\left(x\right) et en évaluant l’identité polynomiale en 1, on obtient :

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

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 est un entier naturel non nul, 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à !


J’espère que cet article vous a plu. Merci de me faire part de vos remarques 🙂

Partager cet article
  • 1
  •  
  •  
  •  
  •  

Laisser un commentaire

Fermer le menu