# What's Combinatorial Proof/Object/etc.?

In high school, when we talked about "combinatorics," we solely meant "mathematics of choice." For instance:

• There are 10 people who want to sit around a table. In how many ways is this possible?
• We have 50 balls and 20 boxes. In how many ways can we distribute balls into the boxes?
• There are 10 apples and 5 oranges. In how many ways can we select 7 fruits?
• ...

I did have this certain wrong view of combinatorics unless I read about combinatorial objects (lists, sets, graphs, etc.) and combinatorial proofs. I tried reading several sources (Wikipedia, books, papers), but still don't have a clear understanding of when something is called combinatorial.

-
Combinatorics is mathematics of counting. – Quixotic Dec 13 '10 at 13:24
And a combinatorial proof is a certain kind of proof which is especially favored in combinatorics. I think it's hard to improve on Wikipedia's explanation: en.wikipedia.org/wiki/… – Samuel Dec 13 '10 at 14:26
When I think about a combinatorial proof, I usually think about proof by bijection or proof by double counting. – PEV Dec 13 '10 at 15:57

There are several different branches of combinatorics but in general they deal with discrete structures.

Enumerative combinatorics, as the name suggests, deals with counting, so the combinatorics you learn in school mostly falls into this category, asking you for the number of permutations or combinations in a particular situation. Extremal combinatorics, for another example, asks for the largest or smallest structure satisfying certain properties. These terms are deliberately vague to allow for generality.

A combinatorial proof is simply a proof using a combinatorial argument. For example, one can prove the binomial theorem using mathematical induction or using a combinatorial argument, in which case what is to be justified is the coefficient of the various terms which is to be obtained by counting in some way.

-
I specially liked this answer for contrasting between enumerative combinatorics and extremal combinatorics, and pointing to the fact that "these terms are deliberately vague to allow for generality." – M.S. Dousti Dec 14 '10 at 3:53

A combinatorial argument often consists in giving a bijection between two sets or at least has such an observation as its key step. More precisely, one often starts with one set $A$ whose elements one wishes to count. You then find a bijection from $A$ to some other set $B$ whose elements are easily counted, leading to some expression for the number of elements of $A$.

A very simple example would be the problem of counting the number of subsets of some finite set of size $n$; call this set of subsets $A$. We first notice there's a bijection from $A$ to the set $B$ of length $n$ binary strings. We can easily count the number of elements of $B$; it's just $2^n$. Hence $A$ also has $2^n$ elements.

More generally, a combinatorial argument proceeds by noticing that some statement to be proved is equivalent to the assertion that two sets are in bijection and then by constructing an explicit bijection.

-