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 - The Fusion of Science and Community**

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

# Number of even/odd subsets.

Loading...

Similar Threads - Number subsets | Date |
---|---|

B Problem in Counting - Number of Passwords | Feb 23, 2018 |

I Partitioning a whole number in a particular way | Feb 14, 2018 |

I Combination of Non Adjacent Numbers | Dec 3, 2017 |

I Problem with infinite decimal numbers? | Oct 23, 2017 |

B Subsets of Rational Numbers and Well-Ordered Sets | May 31, 2017 |

**Physics Forums - The Fusion of Science and Community**