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

Dismiss Notice

Join Physics Forums Today!

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

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