- #1
Apogee
- 45
- 1
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 said: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?
Bacle2 said: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.
Office_Shredder said: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:
[tex] (x+y)^{n} = \sum_{k=0}^{n} {n \choose k} x^{k} y^{n-k} [/tex]
Proof:
[tex] (x+y)^{n} = (x+y)(x+y)(x+y)...(x+y) [/tex]
When we expand the right hand side by repeated distribution, we get a sum of terms of the form [itex] x^{k} y^{j}[/itex]. 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 [itex] x^{k} y^{n-k}[/itex]. Furthermore, to get an [itex] x^{k} y^{n-k}[/itex] we must choose k of the (x+y)'s to pick an x from, and pick a y from the rest. There are [itex] {n \choose k}[/itex] ways to do this, so we get [itex] {n\choose k}[/itex] terms of the form [itex] x^{k} y^{n-k} [/itex]. Therefore when we add up all the terms we can express them as
[tex] \sum_{k=0}^{n} {n \choose k} x^{k} y^{n-k} [/tex]
A combinatorial proof is a mathematical method that uses counting and combinatorial techniques to prove the validity of a mathematical statement or equation. It is used to show that two expressions are equal by demonstrating that they count the same set of objects or outcomes.
Combinatorial proofs use counting and combinatorial techniques to prove a statement, while algebraic proofs use algebraic equations and manipulations. Combinatorial proofs are often considered more intuitive and visual, while algebraic proofs are more abstract and symbolic.
Some common examples of combinatorial proofs include the proof of the binomial theorem, the proof of the sum of arithmetic series, and the proof of the number of subsets of a set.
Combinatorial proofs are useful in mathematics because they provide an alternative way to prove mathematical statements, often providing more intuitive and visual explanations. They also help to deepen our understanding of mathematical concepts and relationships between different expressions.
Yes, combinatorial proofs are always valid as long as they follow the rules of combinatorics and counting. However, it is important to note that not all statements can be proven using combinatorial techniques, and some may require other methods such as algebraic or geometric proofs.