How Do Combinatorial Proofs Work?

[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.

 

[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?

 

[Apogee]

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?

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?

 

[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.

Is this O.K; I'm not sure I answered your question.

 

[Apogee]

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.

Is this O.K; I'm not sure I answered your question.

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

 

[Office_Shredder]

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}$$

 

[Apogee]

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}$$

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