Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Number of even/odd subsets.

  1. Feb 20, 2010 #1
    Given a finite set [tex]S[/tex] of cardinality m:
    Decide how many even or odd subsets there are of S (finding one should give you the other).

    Here is what I've done so far.

    First, I looked to a multiplication out by hand.

    (m * (m-1)) + (m * (m-1) * (m-2) * (m-3)) + (m * (m-1) * (m-2) * (m-3) * (m-4) * (m-5)) + ...

    Well, I noticed I could factor (m * (m-1)) out which gives

    (m * (m-1)) * (1 + ((m-2) * (m-3)) + ((m-2) * (m-3) * (m-4) * (m-5)) + ...)

    Inside the second group of parenteses I noticed I could factor out ((m-2) * (m-3)) and so on

    (m * (m-1)) * (1 + ((m-2) * (m-3) * (1 + ((m-4) * (m-5) * (1 + .... )))))))

    Because this was a tad ugly I made a recurrence relation from it

    [tex]R_{k} = 0[/tex]
    [tex]R_{i} = (m-2i)(m-2i-1)(1+R_{i+1})[/tex]
    [tex]R_{0}[/tex] would give the solution for the number of even subsets.

    I can't seem to find the closed form.

    This is the only direction I've gone with the problem so far.

    Does anyone have any directions to go on this or a previously published solution to the problem? I looked all over and couldn't find one but it's the kind of problem I would expect to have already been solved.
     
  2. jcsd
  3. Feb 20, 2010 #2
    Solved it.

    Heh. Silly to have missed it.

    [tex]2^{m-1}[/tex] even subsets and odd subsets.
     
  4. Feb 20, 2010 #3
    Remember that the number of subsets (of a set with m elements) with k elements is given by:

    [tex]\binom{m}{k}[/tex]

    Now, from the binomial theorem (or the fact that there are as many odd subsets as even ones) and the fact that the total number of subsets is 2m, you should be able to deduce that the number of odd subsets is:

    [tex]\sum_{k\;odd}\binom{m}{k}=2^{m-1}[/tex]
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook