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.
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).
, 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. The two ways of counting give the equation and after division by k!
ways to permute this set of size k. Next, order the n − k people who must remain outside into a single-file line so that later they can enter one at a time, as the others leave.
Stanley (1997) gives an example of a combinatorial enumeration problem (counting the number of sequences of k subsets S1, S2, ... Sk, that can be formed from a set of n items such that the intersection of all the subsets is empty) with two different proofs for its solution.
The first proof, which is not combinatorial, uses mathematical induction and generating functions to find that the number of sequences of this type is (2k −1)n. The second proof is based on the observation that there are 2k −1 proper subsets of the set {1, 2, ..., k}, and (2k −1)n functions from the set {1, 2, ..., n} to the family of proper subsets of {1, 2, ..., k}.
Aigner and Ziegler list four proofs of this theorem, the first of which is bijective and the last of which is a double counting argument.
Any tree can be uniquely encoded into a Prüfer sequence, and any Prüfer sequence can be uniquely decoded into a tree; these two results together provide a bijective proof of Cayley's formula.
An alternative bijective proof, given by Aigner and Ziegler and credited by them to André Joyal, involves a bijection between, on the one hand, n-node trees with two designated nodes (that may be the same as each other), and on the other hand, n-node directed pseudoforests.
By finding a bijection between trees with two labeled nodes and pseudoforests, Joyal's proof shows that Tn = nn − 2.
In this proof, Pitman considers the sequences of directed edges that may be added to an n-node empty graph to form from it a single rooted tree, and counts the number of such sequences in two different ways.
And by counting the number of ways in which a partial sequence can be extended by a single edge, he shows that there are nn − 2n!
Equating these two different formulas for the size of the same set of edge sequences and cancelling the common factor of n!