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

Double comptage

Période historique : Pratique combinatoire intemporelle

Démontrer une égalité combinatoire en dénombrant un même ensemble de deux façons différentes.

Contenu & Formulation mathématique

Principe de la démarche
Établissement d'une identité algébrique par dénombrement croisé d'une même relation binaire.
Champs d'application canoniques
Démonstration d'identités binomiales, théorie des graphes et dénombrement de structures discrètes.
∑x∈Xdeg⁡(x)=∑y∈Ydeg⁡(y)=∣E∣\sum_{x \in X} \deg(x) = \sum_{y \in Y} \deg(y) = |E|

Genèse & Portée historique

Technique de preuve d'une élégance suprême consistant à compter la cardinalité d'un ensemble de paires ou de relations selon deux perspectives différentes (par exemple en sommant d'abord par lignes puis par colonnes dans une matrice d'incidence). Les deux expressions obtenues étant égales, l'identité cherchée est prouvée sans aucun calcul lourd.

Le lemme des poignées de main d'Euler (la somme des degrés des sommets d'un graphe vaut deux fois le nombre d'arêtes) est l'une des applications les plus célèbres du double comptage.

« Regarder le même paysage depuis deux collines différentes pour vérifier que rien n'a disparu. »

Filiations & Relations conceptuelles (1)

S'applique à#048

Fonctions génératrices

Les coefficients s'obtiennent par identification combinatoire de développements croisés.

Objet de collection MathTCG

#066
★Commune
⊦

Double comptage

Maths Discrètes•MÉTHODE

Principe : Établissement d'une identité algébrique par dénombrement croisé d'une même relation binaire.

∑x∈Xdeg⁡(x)=∑y∈Ydeg⁡(y)=∣E∣\sum_{x \in X} \deg(x) = \sum_{y \in Y} \deg(y) = |E|
Pratique combinatoire intemporelle

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

Extension : Foundations (#066 / 200)
Numéro global MathTCG : MathTCG #066 / 500
Rareté officielle : Commune (★)
Domaine théorique : Maths Discrètes
Identifiant pérenne : double-comptage
Consulter mon classeurExplorer tout le recueil