Given a finite set [tex]S[/tex] of cardinality m:(adsbygoogle = window.adsbygoogle || []).push({});

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.

**Physics Forums | Science Articles, Homework Help, Discussion**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Number of even/odd subsets.

**Physics Forums | Science Articles, Homework Help, Discussion**