Talk:Double counting (proof technique)

Untitled

The article begins as follows:

In combinatorics, double counting, also called two-way counting, is a proof technique that involves counting the size of a set in two ways in order to show that the two resulting expressions for the size of the set are equal. Such a proof is sometimes called a bijective proof, when it depends on showing the existence of a bijective mapping. That is, we may consider what we are doing to be taking a finite set X and counting it by method A and then method B; or we may also take two sets X and Y and count them both, then show by means of a bijection f from X to Y that the results are the same. The abstract difference in presentation can usually be absorbed in the freedom to count in various ways.

It seems to me that this confuses two different things with each other. (1) In bijective proofs one finds a bijection between two different sets. (2) In double counting, one counts the members of just one set in two different ways. If these are really both the same thing, that should be explained. Michael Hardy 23:27, 11 Mar 2005 (UTC)

Another opinion

Actually, there are two pricinples involved under the same name. I will explain them detail in the next days when I find some spare time.

1. Bijective proof. One has to find bijection (one to one and onto mapping f:A -> B. This proves that |A| = |B|.

1. Bookkeper's rule. Take a matrix M. The sum of elements of M can be computed in two ways.

1. Take the sum of each row and then the sum of all row-sums. 2. Take the sum of each columns and then take the sum of all column-sums. Tomo 23:47, 11 Mar 2005 (UTC)

Proposed Clarification

Please give me feeback on this. Because combinatorics are not very well introduced to the general mathematics-using community, I think we can afford to explain slightly redundantly.

In combinatorics, double counting, also called two-way counting, is a proof technique that involves counting the size of a set S in two ways in order to show that the two resulting expressions for the size of the set are equal. We describe a finite set X from two perspectives leading to two distinct expressions. Through the two perspective, we demonstrate that each is to equal |X|.

Such a proof is sometimes called a bijective proof because the process necessarily provides a bijective mapping between two sets. Each of the two sets is closely related to its respective expression. This free bijective mapping may very well be non-trivial; in certain theorems, the bijective mapping is more important than the expressions' equivalence.

--Yiliu60 02:56, 26 May 2005 (UTC)

I disagree. (Respectfully as always.) I've had a long hard think about this, and my conclusion is that "double counting" and "bijective proof" are quite different concepts. In this I agree with Michael Hardy's comments above ("It seems to me that this confuses two different things with each other..."). If someone can give me a clear explanation of why they think double counting necessarily involves a bijective proof, I'd greatly appreciate it.

I would add that I think "combinatorial proof" is a more general concept that encompasses both "double counting" and "bijective proof" and possibly more. Currently the article combinatorial proof does not reflect this. I have tried and failed to more clearly express what I think the term "combinatorial proof" covers. Any ideas are welcome.

Dmharvey Talk 01:54, 24 Jun 2005 (UTC)

it seems from the definition that double-counting is a special case of a bijective proof -- instead of considering two sets we're considering bijections between a set and itself (trivial, of course). [analogy: isomorphisms between two groups and isomorphisms from a group onto itself.] perhaps this should be clarified in the paragraph entitled "bijective proof"?

of course, a bijective proof that considers two different sets is more interesting -- we have two sets that seem apparently unrelated (so that expressions of their cardinality seem unrelated), and we find a bijection between the sets, thus demonstrating the equality of their cardinalities. when we're double-counting, our method is to determine the cardinality of a set two different ways; when we're proving things bijectively, our method is to find that bijection. both give the same type of result though -- allowing us to equate two different expressions.

Mlord 13:29, 25 February 2006 (UTC)

I imagine the strategic relationship between these methods is more inverse than special case.

In the "forming committees" example, one doesn't really have an automorphism on the set of possible committees. Instead one has a bijection between (disjoint union of sets of possible committees of a given size, taken over all sizes) and (product of sets of possible ways to include a given person, taken over all people). The extra structure gives us the different expressions of cardinality; the bijection gives us the equals sign.

So while there is an interesting bijection implicit in the argument, it doesn't go from any set to itself. You can't ask what are its fixed points, or what its fourth iteration looks like. Melchoir (talk) 09:29, 18 October 2008 (UTC)

Proposed split

I suggest that the mathematics discussion be separated from the accounting discussion. -- Dominus 02:38, 10 April 2006 (UTC)

I have moved the accounting discussion to double counting (accounting). -- Dominus 18:46, 24 April 2006 (UTC)

JA: There should have been more discussion of this before the move. It's generally preferable to use the "most generic disambiguator" for a term, and also to use a discipline name or a field name if those will do. That would suggest Double counting (mathematics) as a 1st choice and Double counting (combinatorics) as a 2nd choice before Double counting (proof technique). The move to the first option is blocked by previous history, so I will put in a move request for that. Jon Awbrey 20:36, 2 August 2006 (UTC)

Note that I did not create Double counting (proof technique) back in April; I did what I described above, and moved the accounting stuff to Double counting (accounting) while leaving the mathematical discussion at Double counting (with no qualifier). -- Dominus 14:07, 3 August 2006 (UTC)

I'm the one who added the qualifier; a complete description of the movements appears below. Stebulus 18:52, 3 August 2006 (UTC)

JA: Aside from all that, the article is badly confounding two different things, "bijective proofs" and "counting two ways". Jon Awbrey 20:48, 2 August 2006 (UTC)

Oops. I totally missed your comments here, JA. Earlier today I turned Double counting into a disambiguation page, moved its prior content to Double counting (proof technique), split off the section on the fallacy to Double counting (fallacy), and changed Double-counting into a redirect to Double counting. (The hyphenated version was originally about accounting, which is in Double counting (accounting).) All this seemed like the obvious thing to do... I now see that I should have checked here for prior conversation on the topic. Well. Now that we're here, any comments or objections? Stebulus 22:46, 2 August 2006 (UTC)

JA: I did spend a decade or two in combinatorics, and I've since learned how much it is possible to forget, so I'll just say what I remember off the cuff and go check some references later. The way I remember it (TWIRI), "counting two ways" was easy, and regarded more as an enumeration trick — the prime example in my neck of the woods would have been the Burnside–Cauchy–Frobenius orbit counting lemma — while "bijective proofs" were hard, and the object of earnest butterfly-chasing in many cases. Of course, everything in mathematics involves proof, so calling it a proof technique is a tautology, but counting two ways was not primarily thought of that way in practice. If memory serves me not too fuzzily, then, there will be some sorting out yet to be done here. Jon Awbrey 12:40, 3 August 2006 (UTC)

I look forward to learning what you find in your references. In the meantime:

• I agree that counting two ways and bijective proofs are separate topics. (In fact, I don't even see why counting two ways necessarily involves constructing a bijection from a set to itself, as the current version of this article claims. What, for example, is the bijection in the article's proof of the handshaking lemma?)
• I'm not sure what you mean when you say that "calling [double counting] a proof technique is a tautology". My guess: since every mathematical technique is a proof technique, the phrase "proof technique" is redundant and should be shortened to "technique", making the article title "Double counting (technique)". Is this what you mean?
• I see above your comment that the most generic qualifier is preferred, so "(mathematics)" or "(combinatorics)" would be better than "(proof technique)". The reason I didn't do that: the topic of Double counting (fallacy) is, it seems to me, totally unrelated to counting two ways, and hence deserves its own article; but both topics fall under mathematics, even under combinatorics.

Stebulus 18:52, 3 August 2006 (UTC)

...Fast forward to late 2008 and there's still no explanation about non-trivial bijections from the set to itself. I'm boldly removing that paragraph. Melchoir (talk) 08:59, 18 October 2008 (UTC)

New section

It would be great to have here the Pitman's double counting proof of the Cayley formula. Igorpak (talk) 07:39, 12 February 2009 (UTC)

That's in Proofs from THE BOOK, right? I'll have to look that up once I get back to my office where my copy is. Thanks for the suggestion. —David Eppstein (talk) 08:14, 12 February 2009 (UTC)

I disagree with the Fermat example, it's really not a double counting argument as I understand it (you don't really enumerate the same large collection of objects in two different way - rather use the algebraic structure of the collection). If you include such examples, you can include just about every pigeonhole principle type proof. A much better example is the proof of the Dehn-Somerville equations at e.g. in chapter 8 of my book.[1] In fact, another good example is the standard proof of the Cauchy theorem (see Aigner & Ziegler or my book, chapter 26, or just about any other geometry textbook). Hope this helps. Igorpak (talk) 22:26, 14 February 2009 (UTC)

I was thinking of the Fermat example as counting the set of bracelets in two ways: A^p-A = p(# of orbits). But it's a matter of interpretation, I guess. I'll take a look at those other examples.

By the way, although it's not hard to find examples of double counting, it's harder to find much in the way of commentary about the method. The start of the chapter on this method in Matousek and Nesetril's discrete math book, for instance, suggests that it derives from an accounting method of adding matrices of numbers in two different orders to double-check the results, but I'm not sure whether I should consider that to be an attempt at serious historical scholarship. It would be nice to say something more in the article than just listing examples. —David Eppstein (talk) 22:45, 14 February 2009 (UTC)

I remember asking Gil Kalai what did he mean by this quote:

Counting pairs is the oldest trick in combinatorics... Every time we count pairs, we learn something from it. [2]

If I recall correctly, I think he told me that he meant double counting proofs. This may not work as a WP justification, but I thought you might like to know. Igorpak (talk) 01:30, 16 February 2009 (UTC)

Whatever you use, can someone please change the first example to something that doesn't involve hypercubes? Half of the challenge to understanding math is not being scared away by big words, I would like more people to not be sacred away : ) --Indolering (talk) 22:04, 10 December 2011 (UTC)