- #1
jdinatale
- 155
- 0
I found an example like the problem asks, but I'm still trying to show the first part. You want the maximum number of subsets such that you can guarantee none are pairwise disjoint.
I'm trying to apply my specific case to the whole problem. For a set with 3 elements, I chose all of the sets with 2 elements, [itex]\binom{3}{2}[/itex] and all of the sets with 3 elements, [itex]\binom{3}{3}[/itex], which is 4 sets.
In general, for an set with n elements, would I want to choose all sets of with n - 1 elements, which would be [itex]\binom{n}{n - 1} = n[/itex] of them and the set with n elements which there is [itex]\binom{3}{3} = 1[/itex] of them.
But that's only n + 1 sets, when I want 2^{n - 1} sets.
I know that [itex]\binom{n}{0} + \binom{n}{1} + \binom{n}{2} + ... + \binom{n}{n} = 2^n[/itex], which is really close to what I want to show.
http://i3.photobucket.com/albums/y89/jdinatale/Joseph-5.png [Broken]
I'm trying to apply my specific case to the whole problem. For a set with 3 elements, I chose all of the sets with 2 elements, [itex]\binom{3}{2}[/itex] and all of the sets with 3 elements, [itex]\binom{3}{3}[/itex], which is 4 sets.
In general, for an set with n elements, would I want to choose all sets of with n - 1 elements, which would be [itex]\binom{n}{n - 1} = n[/itex] of them and the set with n elements which there is [itex]\binom{3}{3} = 1[/itex] of them.
But that's only n + 1 sets, when I want 2^{n - 1} sets.
I know that [itex]\binom{n}{0} + \binom{n}{1} + \binom{n}{2} + ... + \binom{n}{n} = 2^n[/itex], which is really close to what I want to show.
http://i3.photobucket.com/albums/y89/jdinatale/Joseph-5.png [Broken]
Last edited by a moderator: