Formule du crible de Poincaré
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

En combinatoire, la formule du crible de Poincaré ou formule de Poincaré, appelée aussi formule du crible est une relation entre le cardinal d'une réunion d'un nombre fini d'ensembles et les cardinaux de leurs intersections.

Théorème (Un théorème est une proposition qui peut être mathématiquement démontrée, c'est-à-dire une assertion qui peut être établie comme vraie au travers d'un raisonnement logique construit à...)

Soient A1, ..., An n ensembles finis. Nous avons

\left|\,\bigcup_{i=1}^n A_i\,\right|=\sum_{i=1}^n\left|A_i\right| -\sum_{(i,j)\,/\,1\leq i<j\leq n}\left|A_i\cap A_j\right|+\sum_{(i,j,k)\,/\,1\leq i<j<k\leq n}\left|A_i\cap A_j\cap A_k\right|-\ \cdots\cdots\ +(-1)^{n-1}|A_1\cap\ldots\cap A_n|

où |A| désigne le cardinal d'un ensemble fini (En mathématiques, un ensemble E est dit fini si et seulement si E est vide ou s'il existe un entier n et une bijection de E dans l'ensemble des n premiers entiers naturels.) A.

Cette formule peut aussi s'écrire de façon plus condensée

\left|\,\bigcup_{i=1}^n A_i\,\right|=\sum_{k=1}^n \left((-1)^{k-1} \sum_{1\leq i_1<i_2<\ldots<i_k\leq n} \left|A_{i_1}\cap A_{i_2}\cap \ldots \cap A_{i_k}\right|\right).

Elle peut se démontrer par récurrence sur n, ou en utilisant les fonctions indicatrices.

Cas particulier

Considérons par exemple, le cas n = 2. Soient A et B deux ensembles finis, la formule s'écrit

|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 (La Réunion est une île française du sud-ouest de l'océan Indien située dans l'archipel des Mascareignes à environ 700 kilomètres à l'est de Madagascar et à 170 kilomètres...) de deux ensembles A et B en additionnant les cardinaux de ces deux ensembles et en soustrayant le cardinal de leur intersection.

Le principe est basé sur une inclusion généreuse, suivie d'une exclusion compensatrice (principe d'inclusion exclusion de Moivre.)

Quand n > 2, l'exclusion des cardinaux des intersections de paires d'ensembles est trop forte (en général), et est corrigée par l'addition (L'addition est une opération élémentaire, permettant notamment de décrire la réunion de quantités ou l'adjonction de grandeurs extensives de même...) et la soustraction (La soustraction est l'une des opérations basiques de l'arithmétique. La soustraction combine deux ou plusieurs grandeurs du même type,...) de cardinaux d'un nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) supérieur d'ensembles, d'où l'alternance de signes dans la formule générale.

Applications

L'application la plus connue de la formule du crible est sans doute, en combinatoire (En mathématiques, la combinatoire, appelée aussi analyse combinatoire, étudie les configurations de collections finies d'objets ou les combinaisons...), la détermination du nombre de dérangements d'un ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une multitude qui peut être comprise comme un tout », comme...) fini.

Un dérangement d'un ensemble A est une bijection (Une fonction f: X → Y est dite bijective ou est une bijection si pour tout y dans l’ensemble d'arrivée Y il existe un et un...) de A sur lui-même sans point fixe (En mathématiques, pour une application f d’un ensemble E dans lui-même, un élément x de E est un point fixe de f si f(x) = x.).

Grâce au principe d'inclusion-exclusion de Moivre, nous pouvons prouver que si le cardinal de A est égal à n, alors le nombre de dérangements de A est le nombre entier le plus proche de \frac{n!}{e} (où e désigne la base des logarithmes népériens).

Il s'ensuit que si toutes les bijections ont la même probabilité (La probabilité (du latin probabilitas) est une évaluation du caractère probable d'un évènement. En mathématiques, l'étude des probabilités est un sujet de grande importance donnant lieu à de...) d'être choisies, alors la probabilité pour qu'une bijection prise au hasard (Dans le langage ordinaire, le mot hasard est utilisé pour exprimer un manque efficient, sinon de causes, au moins d'une reconnaissance de cause à effet d'un événement.) soit un dérangement tend rapidement vers 1/e lorsque n tend vers l'infini (Le mot « infini » (-e, -s ; du latin finitus, « limité »), est un adjectif servant à qualifier quelque chose qui n'a pas de limite en nombre ou en taille.).

Dans beaucoup de cas (en particulier, dans le comptage des nombres premiers inférieurs à un entier donné grâce au crible d'Ératosthène), la formule de Poincaré n'est pas d'une grande utilité parce que le nombre de termes qu'elle comporte s'avère excessif. Si chacun des termes de la somme peut être évalué de façon exacte, une accumulation des erreurs de calcul dans les additions peut rendre la formule inapplicable.

En théorie (Le mot théorie vient du mot grec theorein, qui signifie « contempler, observer, examiner ». Dans le langage courant, une théorie est une idée ou une connaissance spéculative, souvent basée...) des nombres, cette difficulté fut soulevée par Viggo Brun. Beaucoup plus tard, ses idées furent reprises par d'autres mathématiciens, et de nombreuses variétés de méthodes du crible furent développées. Par exemple, certaines d'entre elles permettent d'encadrer très finement les cardinaux d'ensembles " criblés ", plutôt que de donner une valeur exacte avec une formule trop lourde. De tels encadrements s'obtiennent en remarquant que la somme des premiers termes de la formule du crible est alternativement un majorant et un minorant du cardinal de la réunion.

Page générée en 0.051 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique