Principe d'inclusion-exclusion
Le principe d'inclusion-exclusion permet de déterminer la taille d'une union d'ensembles en additionnant et soustrayant alternativement les tailles de leurs intersections.
Definition
Une identité de dénombrement stipulant que la cardinalité d'une union d'ensembles finis est égale à la somme alternée des cardinalités de toutes leurs intersections, prises sur chaque sous-collection non vide.
Scope
Ce sujet présente la formule d'inclusion-exclusion et ses applications au dénombrement d'objets qui évitent une liste de propriétés interdites : les dérangements, les surjections, l'indicatrice d'Euler (ou fonction totient d'Euler), et le nombre d'entiers premiers avec un nombre donné. Il introduit la perspective du crible et la généralisation de la fonction de Möbius sur les ensembles partiellement ordonnés, ce qui inscrit le principe dans un cadre algébrique plus large.
Core questions
- Combien d'éléments satisfont au moins une de plusieurs conditions qui se chevauchent ?
- Comment peut-on dénombrer des objets évitant toutes les propriétés d'un ensemble de propriétés interdites ?
- Comment les dénombrements de dérangements et de surjections découlent-ils du principe ?
- Comment la fonction de Möbius sur un ensemble partiellement ordonné généralise-t-elle l'inclusion-exclusion ?
Key concepts
- Union d'ensembles qui se chevauchent
- Méthode du crible
- Dérangements via l'inclusion-exclusion
- Dénombrement des surjections
- Fonction indicatrice d'Euler
- Fonction de Möbius sur les ensembles partiellement ordonnés
Key theories
- Formule d'inclusion-exclusion
- La cardinalité d'une union d'ensembles A_1 à A_n est égale à la somme des tailles des ensembles individuels moins les intersections par paires plus les intersections par triplets, et ainsi de suite, corrigeant systématiquement le surcomptage des éléments partagés.
- Inversion de Möbius sur les ensembles partiellement ordonnés
- La généralisation de Stanley, basée sur la théorie des ensembles partiellement ordonnés, remplace les signes alternés de l'inclusion-exclusion par la fonction de Möbius d'un ensemble partiellement ordonné, unifiant ainsi le principe avec les formules d'inversion de la théorie des nombres et de la théorie des treillis.
Clinical relevance
L'idée du crible se généralise à la théorie des nombres (le crible d'Ératosthène et les cribles analytiques), aux probabilités (les inégalités de Bonferroni bornant les probabilités d'union), et à l'analyse de fiabilité des systèmes avec des modes de défaillance qui se chevauchent.
History
Énoncé en substance par de Moivre et Sylvester, le principe a été intégré dans une théorie générale des fonctions de Möbius sur les ensembles partiellement ordonnés par Rota en 1964, marquant un jalon de la combinatoire moderne.
Key figures
- Abraham de Moivre
- Gian-Carlo Rota
Related topics
Seminal works
- stanley2011
Frequently asked questions
- Pourquoi les signes sont-ils alternés ?
- Les éléments appartenant à plusieurs ensembles sont ajoutés trop de fois ; soustraire les intersections par paires corrige excessivement, de sorte que les intersections par triplets sont rajoutées, produisant le motif alterné qui compte chaque élément exactement une fois.
- Quel est le lien avec la fonction de Möbius ?
- L'inclusion-exclusion est le cas particulier de l'inversion de Möbius sur le treillis booléen des sous-ensembles, où la fonction de Möbius prend les valeurs plus ou moins un.