Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Combinatorial proof
Summary
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.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.