
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 le cardinal d’un ensemble fini
.
Il est connu que si et
sont deux ensembles finis, alors :
On comprend cette formule en considérant que l’expression fournit une « sur-évaluation » de
dans la mesure où les éléments de l’intersection sont tous comptés deux fois. On rectifie donc le tir en retranchant
De la même manière, si ,
et
sont trois ensembles finis, l’expression
donne un majorant de
puisque certains éléments sont comptés deux fois (ceux qui appartiennent à deux des
mais pas aux trois) voire trois fois (ceux qui appartiennent aux trois), d’où la formule :
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 ensembles finis
, si l’on note pour tout
:
Remarque 1
Si par exemple , alors :
Remarque 2
Revenons à n quelconque.
L’entier est la somme des cardinaux des intersections
à
des
En particulier :
Noter que la somme qui définit comporte
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é , le second membre est « tronqué », c’est-à-dire si l’on n’en conserve que les
premiers termes (pour un certain
), alors on obtient une inégalité. Plus précisément :
Théorème 2 (inégalités de Bonferroni)
Si sont des ensembles finis, alors :
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 est très classique :
Théorème 3 (inégalité de Boole)
Si sont des ensembles finis, alors :
Preuve (cliquer pour déplier / replier)
On prouve aisément ceci par récurrence.
Pour , il n’y a rien à démontrer. Pour
, on sait que :




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 des réels positifs (avec
). On suppose qu’il existe
tel que
soit croissante et
soit décroissante. Si de plus :

Preuve (cliquer pour déplier / replier)
Supposons .
➡ Si est pair, alors en posant
:
➡ Si


Supposons maintenant . On constate que :

La dernière somme est du signe de , donc
est du signe de
.
Corollaire (Application du Lemme 1 aux coefficients binomiaux)
Pour donné, la suite finie de terme général
(pour
) est d’abord croissante, jusqu’au terme d’indice
, puis décroissante.
De plus :
Donc, en appliquant le lemme précédent :
Ce résultat peut toutefois être obtenu directement car :
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 des ensembles finis et
Pour tout
, on note :
Par ailleurs, si , on note :
Alors, pour tout et pour tout
:
Preuve (cliquer pour déplier / replier)
En notant , on voit que :
où



et le résultat en découle puisque .
Lemme 3
Soient des ensembles
et
un ensemble contenant chacun des
.
Alors, la fonction indicatrice de l’union des est donnée par :
Preuve (cliquer pour déplier / replier)
Pour tout :
donc :
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) :
En remplaçant, pour chaque , le coefficient
par
et en évaluant l’identité polynomiale en 1, on obtient :
d’où le résultat, d’après .
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 :
D’après le lemme 2, en notant toujours

c’est-à-dire :
Enfin, d’après le lemme 1 et son corollaire, chacune des sommes internes est du signe de


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 de l’ensemble
, où
, possède la propriété
s’il existe au moins un indice
tel que
Prouver que, pour tout le nombre de permutations possédant la propriété
est supérieur au nombre de celles qui ne la possèdent pas.
Dans ce contexte, si , on appelle « permutation de l’ensemble
» toute liste de longueur
constituée exactement des entiers de
à
mais dans un ordre quelconque. Il est bien connu qu’il existe
telles permutations.
Cela dit, notons l’ensemble des permutations de l’ensemble
, pour lesquelles
et
occupent des positions contigües (avec
).
Par exemple, pour , les permutations
et
appartiennent à
puisque
et
se retrouvent côte à côte; alors que la permutation
n’appartient pas à
.
Mais revenons au cas général…
Le nombre de permutations de possédant la propriété
est :





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


Or, manifestement :
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.