∑
MathTCG
#055 / 200•Foundations•MathTCG #055 / 500•★★Peu commune•⊦Maths Discrètes•Méthode & Idée

Principe d'inclusion-exclusion

Période historique : 1708 (Montmort) - 1854 (Sylvester)

La formule de crible alternée pour compter exactement la réunion d'ensembles qui se chevauchent.

Contenu & Formulation mathématique

Principe de la démarche
Correction alternée des surcomptages successifs dans la mesure d'une réunion de domaines non disjoints.
Champs d'application canoniques
Calcul du nombre de dérangements, indicatrice d'Euler φ(n), cribles arithmétiques et probabilités combinatoires.
∣⋃i=1nAi∣=∑k=1n(−1)k−1∑1≤i1<⋯<ik≤n∣Ai1∩⋯∩Aik∣\left| \bigcup_{i=1}^n A_i \right| = \sum_{k=1}^n (-1)^{k-1} \sum_{1 \le i_1 < \dots < i_k \le n} |A_{i_1} \cap \dots \cap A_{i_k}|

Genèse & Portée historique

Formule combinatoire fondamentale permettant de calculer le cardinal de la réunion de plusieurs ensembles finis non disjoints. On additionne d'abord les tailles de chaque ensemble, puis on soustrait les intersections de paires, on rajoute les intersections de triplets, et l'on alterne ainsi jusqu'à l'intersection globale.

Pierre Rémond de Montmort l'employa en 1708 pour résoudre le célèbre 'problème des rencontres' (calculer la probabilité qu'aucun chapeau ne revienne à son propriétaire lors d'un tirage au sort).

« Ajouter, retrancher, puis rajouter encore : le tamis parfait qui ne laisse aucun doublon. »

Filiations & Relations conceptuelles (0)

Cette notice constitue un axiome autonome sans relations directes enregistrées dans le recueil.

Objet de collection MathTCG

#055
★★Peu commune
⊦

Principe d'inclusion-exclusion

Maths Discrètes•MÉTHODE

Principe : Correction alternée des surcomptages successifs dans la mesure d'une réunion de domaines non disjoints.

∣⋃i=1nAi∣=∑k=1n(−1)k−1∑1≤i1<⋯<ik≤n∣Ai1∩⋯∩Aik∣\left| \bigcup_{i=1}^n A_i \right| = \sum_{k=1}^n (-1)^{k-1} \sum_{1 \le i_1 < \dots < i_k \le n} |A_{i_1} \cap \dots \cap A_{i_k}|
1708 (Montmort) - 1854 (Sylvester)

Dans l'édition physique et numérique de MathTCG, cette carte appartient à l'extension Foundations.

Extension : Foundations (#055 / 200)
Numéro global MathTCG : MathTCG #055 / 500
Rareté officielle : Peu commune (★★)
Domaine théorique : Maths Discrètes
Identifiant pérenne : principe-d-inclusion-exclusion
Consulter mon classeurExplorer tout le recueil