The Difference Between Bijective and Double Counting Proofs
Stanley does not clearly distinguish between bijective and double counting proofs, and gives examples of both kinds, but the difference between the two types of combinatorial proof can be seen in an example provided by Aigner & Ziegler (1998), of proofs for Cayley's formula stating that there are nn − 2 different trees that can be formed from a given set of n nodes. 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. They also mention but do not describe the details of a fifth bijective proof.
The most natural way to find a bijective proof of this formula would be to find a bijection between n-node trees and some collection of objects that has nn − 2 members, such as the sequences of n − 2 values each in the range from 1 to n. Such a bijection can be obtained using the Prüfer sequence of each tree. 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. If there are Tn n-node trees, then there are n2Tn trees with two designated nodes. And a pseudoforest may be determined by specifying, for each of its nodes, the endpoint of the edge extending outwards from that node; there are n possible choices for the endpoint of a single edge (allowing self-loops) and therefore nn possible pseudoforests. By finding a bijection between trees with two labeled nodes and pseudoforests, Joyal's proof shows that Tn = nn − 2.
Finally, the fourth proof of Cayley's formula presented by Aigner and Ziegler is a double counting proof due to Jim Pitman, presented in more detail in Double counting (proof technique)#Counting trees. 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. By showing how to derive a sequence of this type by choosing a tree, a root for the tree, and an ordering for the edges in the tree, he shows that there are Tnn! possible sequences of this type. 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! possible sequences. Equating these two different formulas for the size of the same set of edge sequences and cancelling the common factor of n! leads to Cayley's formula.
Read more about this topic: Combinatorial Proof
Famous quotes containing the words difference, double, counting and/or proofs:
“Man is the only animal that laughs or weeps; for he is the only animal that is struck with the difference between what things are, and what they ought to be. We weep at what thwarts or exceeds our desires in serious matters; we laugh at what only disappoints our expectations in trifles.”
—William Hazlitt (1778–1830)
“The obsession with suicide is characteristic of the man who can neither live nor die, and whose attention never swerves from this double impossibility.”
—E.M. Cioran (b. 1911)
“What we commonly call man, the eating, drinking, planting, counting man, does not, as we know him, represent himself, but misrepresents himself. Him we do not respect, but the soul, whose organ he is, would he let it appear through his action, would make our knees bend.”
—Ralph Waldo Emerson (1803–1882)
“Would you convey my compliments to the purist who reads your proofs and tell him or her that I write in a sort of broken-down patois which is something like the way a Swiss waiter talks, and that when I split an infinitive, God damn it, I split it so it will stay split, and when I interrupt the velvety smoothness of my more or less literate syntax with a few sudden words of bar- room vernacular, that is done with the eyes wide open and the mind relaxed but attentive.”
—Raymond Chandler (1888–1959)