Talk:Combinatorial proof

The page tries to draw a clear line between double counting and bijective proofs. But since counting is by definition building a bijection with the set $1..n$ for some $n$, technically double counting is a special case of bijective proofs. (Bijections are more generally applicable because they also support uncountable sets.) 2600:1700:38D0:5C00:5D6D:FE0D:8C70:AE2D (talk) 04:55, 19 February 2021 (UTC)

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)

I think "combinatorial proof" is often used in this broader sense, both in various Wikipedia articles and in the broader mathematical literature, but the actual reference I have for the use of that phrase (Stanley) seems to mean it more narrowly. —David Eppstein (talk) 20:38, 14 February 2009 (UTC)

Introduction

The introduction to this topic is way to long and should be changed. There should be an introduction limited to a few lines before the content box. — Preceding unsigned comment added by 193.91.141.107 (talk) 14:42, 8 April 2012 (UTC)

I've restored the introduction of February 2009. I think the old introduction will be more helpful to students and other people new to the subject who come here for enlightenment. (It was for me, and I have some experience with the subject.) It is true that the two main classes of combinatorial proofs described here do not capture every situation. (In the article's Cayley's-formula example, for instance, none of the proofs quite fit into either class of proof, if the descriptions of the classes are taken literally.) But a definition filled with caveats and nuances in an attempt to describe every situation—an impossible task!—is not so good as one's first exposure to the topic. Will Orrick (talk) 16:41, 15 September 2013 (UTC)