# Combinatorial counting problem

1. Oct 12, 2009

### ploppers

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. Oct 12, 2009

### LCKurtz

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?

3. Oct 12, 2009

### Count Iblis

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.

4. Oct 12, 2009

### ploppers

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