1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

How Do Combinatorial Proofs Work?

  1. Jun 16, 2013 #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.
  2. jcsd
  3. Jun 16, 2013 #2


    User Avatar
    Science Advisor

    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?
  4. Jun 16, 2013 #3
    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?
  5. Jun 16, 2013 #4


    User Avatar
    Science Advisor

    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|)+


    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.
    Last edited: Jun 17, 2013
  6. Jun 17, 2013 #5
    Thank you. That was very helpful. I understand how it works in set theory, but how would it apply to number theory?
  7. Jun 17, 2013 #6


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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]

    [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]
  8. Jun 17, 2013 #7
    Oh, okay. I'm kind of getting it, now. Thanks. :)
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook