Example
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. The two ways of counting give the equation
and after division by k! this leads to the stated formula for . In general, if the counting formula involves a division, a similar double counting argument (if it exists) gives the most straightforward combinatorial proof of the identity, but double counting arguments are not limited to situations where the formula is of this form.
Read more about this topic: Combinatorial Proof
Famous quotes containing the word example:
“Our intellect is not the most subtle, the most powerful, the most appropriate, instrument for revealing the truth. It is life that, little by little, example by example, permits us to see that what is most important to our heart, or to our mind, is learned not by reasoning but through other agencies. Then it is that the intellect, observing their superiority, abdicates its control to them upon reasoned grounds and agrees to become their collaborator and lackey.”
—Marcel Proust (1871–1922)