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 Glass (2003) writes in his review of Benjamin & Quinn (2003)
(a book about combinatorial proofs), these two simple techniques are enough to prove many theorems in combinatorics and number theory.
Wikipedia
|