What is a combinatorial proof exactly?

Question

It almost seems as though a combinatorial proof is "Explain the intuition behind this relationship (using normal words) to explain why it is true."

I'm a little lost as to how this is a proof exactly, since I always thought proofs were meant to be very rigorous. I can't think of a counter-example but it seems possible to come up with a combinatorial proof that sounds right but is actually wrong when you get down to the algebra.

Is my understanding correct? Are there any other conditions that a combinatorial proof must meet to be considered a valid proof?

Answer 1

There are typically a few ways to prove a combinatorics question. One common way is to use algebra, where you reduce the given equation or relation using algebra to an identity. Another way is by block-walking where you prove the result using Pascal's triangle. Finally the third way is to use a committee-forming argument where you prove the result using the logic of a committee.

I get what you are saying about combinatorics proofs sometimes not being very rigorous since they seem informal. Sometimes a combinatorial identity can be proved just using words and without equations at all. But there is no one form of doing a combinatorics prove that is more valid than the other.

Answer 2

There are many proofs that need not be rigorous but are right, like the proof for $ |A \cup B| = |A| + |B| - |A \cap B| $, or Bayes theorem. For a combinatorial proof, you need to define first a set S first and then count the it in two different ways and since they count the same set S so they are equal and such proofs are as good as any other rigorous proof.

Using combinatorial proof is usually a much better approach though to remember many identities like the hockey-stick identity or Vandermonde Identity.