# How Do Combinatorial Proofs Work?

1. Jun 16, 2013

### Apogee

Well, the title pretty much sums it up. I was reading up about combinatorial proofs and was wondering if anyone could offer an example of one or explain how they are done.

2. Jun 16, 2013

### Bacle2

Seems like too broad of a question: there are different subbranches. Do you want counting, graph theory, ....

Why don't you start with the inclusion-exclusion principle, or bring up some specific issue you're interested in?

3. Jun 16, 2013

### Apogee

I was thinking more along the lines of number theory, but any example will suffice. I'm just trying to understand when, why, and how to use them to prove certain theorems.

Moreover, do you know how to prove the inclusion-exclusion principle combinatorially?

4. Jun 16, 2013

### Bacle2

Sorry,just getting back from dinner & B&N .

The argument I know basically show that each person is counted exactly once.

For small cases: say you want to count the number of people who either smoke :=S, or
are left-handed:=L .

The formula for inclusion-exclusion is then :

|S\/L|=|S|+|L|-|S/\L| ; |S|:= cardinality of the set S

The argument is that each person in the group S\/L is counted exactly once:

i) If person x smokes but is not lefthanded: then x will be counted exactly once; in |S| .Similar
if person y is lefthanded but does not smoke.

ii) Person z is a lefthanded smoker. Then z will be counted once in |S|; once in |L| --so we have
overcounted z , i.e., we have counted twice. But now we subtract z from the count, because
z is in |S/\L| , which is subtracted from the count. So z is counted exactly 1+1-1 =1 times,
which means we are counting correctly.

Then IE generalizes to:

|A1/\A2/\.../\An|=|A1|+...+|An|- (|A1/\A2|+.....+|An-1/\An|)+

(|A1/\A2/\A3|+....+|An-2/\An-1/\An|)-.....+/-(|A1/\A2.../\An|)

And the proof generalizes too: let x be a person that satisfies j out of the n conditions Ai. We
show that x is counted precisely once in the general formula.

Last edited: Jun 17, 2013
5. Jun 17, 2013

### Apogee

Thank you. That was very helpful. I understand how it works in set theory, but how would it apply to number theory?

6. Jun 17, 2013

### Office_Shredder

Staff Emeritus
Number theory has some combinatorial proofs but most of the useful applications that I'm aware of are for fairly deep results and no amenable to a quick post demonstrating the technique

Here's a simple combinatorial application to algebra. Theorem:
$$(x+y)^{n} = \sum_{k=0}^{n} {n \choose k} x^{k} y^{n-k}$$

Proof:
$$(x+y)^{n} = (x+y)(x+y)(x+y)...(x+y)$$

When we expand the right hand side by repeated distribution, we get a sum of terms of the form $x^{k} y^{j}$. Every term in the sum is found by taking either an x or a y from each (x+y) and multiplying them together. So each term has degree n, meaning it is of the form $x^{k} y^{n-k}$. Furthermore, to get an $x^{k} y^{n-k}$ we must choose k of the (x+y)'s to pick an x from, and pick a y from the rest. There are ${n \choose k}$ ways to do this, so we get ${n\choose k}$ terms of the form $x^{k} y^{n-k}$. Therefore when we add up all the terms we can express them as
$$\sum_{k=0}^{n} {n \choose k} x^{k} y^{n-k}$$

7. Jun 17, 2013

### Apogee

Oh, okay. I'm kind of getting it, now. Thanks. :)