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:
“Friends serve central functions for children that parents do not, and they play a critical role in shaping children’s social skills and their sense of identity. . . . The difference between a child with close friendships and a child who wants to make friends but is unable to can be the difference between a child who is happy and a child who is distressed in one large area of life.”
—Zick Rubin (20th century)
“since I see
Your double heart,
Farewell my part!”
—Sir Thomas Wyatt (1503?–1542)
“What culture lacks is the taste for anonymous, innumerable germination. Culture is smitten with counting and measuring; it feels out of place and uncomfortable with the innumerable; its efforts tend, on the contrary, to limit the numbers in all domains; it tries to count on its fingers.”
—Jean Dubuffet (1901–1985)
“A man’s women folk, whatever their outward show of respect for his merit and authority, always regard him secretly as an ass, and with something akin to pity. His most gaudy sayings and doings seldom deceive them; they see the actual man within, and know him for a shallow and pathetic fellow. In this fact, perhaps, lies one of the best proofs of feminine intelligence, or, as the common phrase makes it, feminine intuition.”
—H.L. (Henry Lewis)