Talk:Combinatorial proof

There is already a double counting page. If combinatorial proof is the more general concept, perhaps that page should be merged into this one.

Charles Matthews 21:25, 21 Jun 2004 (UTC)

It looks like that "double counting" can refer to a fallacy, while "combinatorial proof" cannot. Also, I can't come up a concrete example now, but I worry what if we need to count something in more than two ways, like in a planar graph where you need to count the number of edges and faces incident to a vertex? Would that be still considered "double" counting? or "triple" counting? So I would say "combinatorial proof" is the preferred term as far as the non-fallacy part is concerned. But since it does not really cover all meanings of "double counting", the latter should not be treated as a subset. Perhaps the two pages are better left separated for the time being.
Peter Kwok 15:31, 2004 Jun 22 (UTC)

Confusion on the topics of these three articles

• Bijective proof assumes two given sets, and proves they have the same size by cleverly constructing a bijection.
• Double counting assumes only one given set (so the existence of many bijections is obvious and no cleverness is needed to prove the existence) and proves some combinatorial identity by two different ways of counting the members.

• • In the first case, equinumerosity us not at all obvious initially, and is to be proved;

• • In the second case it is obvious and use is made of it in the final step: putting the "=" between the two sides of the identity.

Until may edits this afternoon, the content and the exmples showed great confusion, as if this had been written by someone who failed to notice that these are two different things. Michael Hardy 22:05, 2 August 2006 (UTC)

Can you count an object?

Both here and under mathematical proof the phrase count[ing] an object is used several times. Something bothers me about this construction. In normal parlance, one can't count an object -- for example, you can't count an apple, you can't count a house. Surely what is meant here is counting a set of objects.

I anticipate the rebuttal that a set is a sort of object, so the sets that are being counted are objects a fortiori. This may be true in a logic-chopping sense, but I don't think we are serving our readers well with our talk of "counting an object two different ways".

I recommend judicious use of phrases like set of objects in these circumstances. I'm not doing the edit this second only because I'm worried that I missed a subtlety here. Comments welcome.

ACW 21:17, 26 Jan 2005 (UTC)

No citation for Jeopardy! proof

I deleted the call for a citation because, all that the passage claims is that the technique has been referred to as Jeopardy! proof, and even that was merely colloquial. I don't feel that such an informal, almost anecdotal comment really requires documentary support. I do feel, however, that the informal comment merits retention in the article because the simile provides a useful analogy to help people understand the idea behind the proof technique.—PaulTanenbaum (talk) 22:01, 23 January 2009 (UTC)

I, on the other hand, just took out the comment because I could find no reliable source for the claim that these proofs are commonly referred to via this phrase. (My other edits to the article today were much more significant, however.) —David Eppstein (talk) 01:57, 14 February 2009 (UTC)

Combinatorial proof and elementary proof

Elementary proof says that "An elementary proof in combinatorics, using methods such as direct enumeration, is similarly called a combinatorial proof", while Combinatorial proof seems to give a more narrow characterisation of a combinatorial proof. — Miym (talk) 20:28, 14 February 2009 (UTC)