1. PF Contest - Win "Conquering the Physics GRE" book! Click Here to Enter
    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!

Combinatorial counting problem

  1. Oct 12, 2009 #1
    1. The problem statement, all variables and given/known data

    Show that there is a one to one correspondence between even and odd subsets of the set {0, 1...n}.

    2. Relevant equations

    They want a combinatorial proof so basically a proof based on counting?
    Perhaps (n choose k) = (n choose n-k)

    3. The attempt at a solution

    I've solved this problem algebraically by expanding (1-1)^n, however, I do not understand, by counting, how there are the same amount of even subsets as odd. I tried expanding the factorials and trying to simplify but it proved to be unsuccessful. This is the 1st problem of the problem set, I have a feeling that the solution is very simple.
  2. jcsd
  3. Oct 12, 2009 #2


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    What does "even subset" mean? Do you mean subsets having an even number of elements or subsets consisting of only even numbers?

    My guess is the second interpretation. And if you show the "even" sets and "odd" sets have the same number of elements, wouldn't that do it?
  4. Oct 12, 2009 #3
    You have:

    0 = (1-1)^n = Sum from k = 0 to n of Binomial[n,k](-1)^k =

    (add up the even and odd k separately) =

    #even subsets - #odd subsets.
  5. Oct 12, 2009 #4
    Even and odd subsets mean choosing an even amount or odd amount. For example, 4 choose 3 would be an odd subset while 4 choose 2 would be even. Thanks for the responses, that was exactly what I did to prove it algebraically, however, what would the combinatorial proof be?

    I've tried to solve the problem further by comparing the relationship between choosing 2i +1 numbers and 2i numbers. (nC2i + 1) = (nC2i)(n - 2i)/(2i + 1). When I sum these, I don't see how they could ever equal...
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook