Preuve par double dénombrement

En mathématiques combinatoires, une preuve par double dénombrement, ou double comptage, ou encore double décompte, est une technique de preuve combinatoire servant à démontrer que deux expressions sont égales en prouvant qu'il y a deux façons de compter le nombre d'éléments d'un même ensemble. Van Lint et Wilson décrivent cette technique comme « un des outils les plus importants en combinatoire ». Soient deux ensembles finis et , et une partie de ; chaque fois que appartient à , on dit que et sont incidents. Notons que peut être vu comme le graphe d'une relation binaire de vers , auquel cas " et incidents" s'écrit , ou encore comme un graphe biparti. Si désigne le nombre d'éléments incidents à , et celui des éléments incidents à , on a alors la formule dite du double décompte, ou du comptage par tranches (ou par piles) : Un cas particulier intéressant est celui où et sont constants ; la formule s'écrit alors . vignette|La formule du double décompte s'écrit dans cet exemple : La formule du double décompte s'interprète dans ce diagramme par le fait que le nombre de flèches est égal au nombre de leurs départs ainsi qu'au nombre de leurs arrivées. Si on définit la matrice d'incidence du graphe ou de la relation par si appartient à , sinon, la formule du double décompte signifie que la somme des termes de la matrice s'obtient soit en sommant lignes par lignes, soit en sommant colonnes par colonnes. En effet est le nombre de situés dans la ligne associée à , et est le nombre de situés dans la colonne associée à . Dans l'exemple ci-contre, la matrice d'incidence est . En ce sens, la formule du double décompte est un cas particulier de la formule d'interversion de signes de sommation : . Ici, les ensembles et sont égaux à l'ensemble des entiers de 1 à , et deux entiers et sont incidents si . Alors et La formule du double décompte s'écrit alors , dont on déduit la formule classique . vignette|300x300px|Courbe du nombre moyen de diviseurs d'un nombre entre 1 et avec, en rouge, la courbe de .|alt= Mêmes ensembles et , mais et sont incidents si divise .

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés (3)

Séances de cours associées (3)

Comptage avancé : preuves combinatoires CS-101: Advanced information, computation, communication I

Déplacez-vous dans les méthodes de comptage avancées, les preuves combinatoires, les relations de récurrence, et le principe généralisé Pigeonhole.

Technique de preuve pour le modèle Spiked PHYS-642: Statistical physics for optimization & learning

Couvre une technique d'épreuve pour le modèle huppé à l'aide de calculs matriciaux et d'évolution de l'état.

Comptage avancé : logique et structures CS-101: Advanced information, computation, communication I

Explore les techniques de comptage avancées telles que le principe du trou de pigeon et les preuves combinatoires.

Preuve par double dénombrement

Preuve par bijection

En mathématiques, une preuve par bijection (ou démonstration par bijection) est une technique de démonstration qui consiste à obtenir l'égalité de deux expressions entières en exhibant une bijection entre deux ensembles dont les deux expressions sont les cardinaux. Autrement dit, on examine deux ensembles finis X et Y, on les dénombre et au moyen d'une bijection de X sur Y, on en déduit que les résultats des comptages sont égaux. On présente souvent la démonstration en disant qu'on a transformé le problème de dénombrement en un problème équivalent.

Combinatoire

En mathématiques, la combinatoire, appelée aussi analyse combinatoire, étudie les configurations de collections finies d'objets ou les combinaisons d'ensembles finis, et les dénombrements. La combinatoire est en fait présente dans toute l'antiquité en Inde et en Chine. Donald Knuth, dans le volume 4A « Combinatorial Algorithms » de The Art of Computer Programming parle de la génération de n-uplets ; il dit que la génération de motifs combinatoires «a commencé alors que la civilisation elle-même prenait forme» (« began as civilization itself was taking shape»).