Talk:Double counting (proof technique)

From Wikipedia, the free encyclopedia

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)

[edit] 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)

[edit] 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)

[edit] 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)