Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Preuve combinatoire
Résumé
In mathematics, the term combinatorial proof is often used to mean either of two types of mathematical proof:
A proof by double counting. A combinatorial identity is proven by counting the number of elements of some carefully chosen set in two different ways to obtain the different expressions in the identity. Since those expressions count the same objects, they must be equal to each other and thus the identity is established.
A bijective proof. Two sets are shown to have the same number of members by exhibiting a bijection, i.e. a one-to-one correspondence, between them.
The term "combinatorial proof" may also be used more broadly to refer to any kind of elementary proof in combinatorics. However, as writes in his review of (a book about combinatorial proofs), these two simple techniques are enough to prove many theorems in combinatorics and number theory.
An archetypal double counting proof is for the well known formula for the number of k-combinations (i.e., subsets of size k) of an n-element set:
Here a direct bijective proof is not possible: because the right-hand side of the identity is a fraction, there is no set obviously counted by it (it even takes some thought to see that the denominator always evenly divides the numerator). However its numerator counts the Cartesian product of k finite sets of sizes n, n − 1, ..., n − k + 1, while its denominator counts the permutations of a k-element set (the set most obviously counted by the denominator would be another Cartesian product k finite sets; if desired one could map permutations to that set by an explicit bijection). Now take S to be the set of sequences of k elements selected from our n-element set without repetition. On one hand, there is an easy bijection of S with the Cartesian product corresponding to the numerator , and on the other hand there is a bijection from the set C of pairs of a k-combination and a permutation σ of k to S, by taking the elements of C in increasing order, and then permuting this sequence by σ to obtain an element of S.
Source officielle
À 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.