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:
“To rescue our children we will have to let them save us from the power we embody: we will have to trust the very difference that they forever personify. And we will have to allow them the choice, without fear of death: that they may come and do likewise or that they may come and that we will follow them, that a little child will lead us back to the child we will always be, vulnerable and wanting and hurting for love and for beauty.”
—June Jordan (b. 1939)
“O, my offense is rank, it smells to heaven;
It hath the primal eldest curse upon ‘t,
A brother’s murder. Pray can I not,
Though inclination be as sharp as will;
My stronger guilt defeats my strong intent,
And like a man to double business bound
I stand in pause where I shall first begin,
And both neglect. What if this cursed hand
Were thicker than itself with brother’s blood,
Is there not rain enough in the sweet heavens
To wash it white as snow?”
—William Shakespeare (1564–1616)
“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)
“I do not think that a Physician should be admitted into the College till he could bring proofs of his having cured, in his own person, at least four incurable distempers.”
—Philip Dormer Stanhope, 4th Earl Chesterfield (1694–1773)