- #1
xnull
- 16
- 0
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.
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.