Question

How many specific pairs of disjoint non empty subsets of G are there, the union of which is all of G? G={1,2,3,4,5}

Answer 1

We can probably just list the possibilities on this one and count them up, but this is inefficient. If the first disjoint set has only one element there are \[\left(\begin{matrix}5 \\ 1\end{matrix}\right)=5\]possible pairs. If the first disjoint subset has 2 members there are\[\left(\begin{matrix}5 \\ 2\end{matrix}\right)=10\]possible pairs. With 3 elements,\[\left(\begin{matrix}5 \\ 3\end{matrix}\right)=10\]4 elements:\[\left(\begin{matrix}5 \\ 4\end{matrix}\right)=5\]We can't pick all five elements because then one disjoint subset would have 5 elements and the other would have to be the empty set, which isn't allowed in your question. So the total should be \[5+10+10+5=30\]possible pairs, if I'm correct.

Answer 2

On second thought I guess making a list of 30 pairings isn't just inefficient, it would be a horrible way to go about solving this :)

Answer 3

In set theory isn't {1,2}U{3,4,5} the same as {2,1}U{3,4,5), so wouldn't you be double counting?

Answer 4

I'm using combinations NOT permutations to count these. If I was using permutations, then yes, we would be double counting.

Answer 5

Yeah, I was thinking it was a combination, but my work is saying that 30 isn't correct.

Answer 6

hmmmmm....let me examine my reasoning.

Answer 7

It turns out you doubled it. The answer is 15

Answer 8

Yeah but why? Shouldn't using combs correct for this?

Answer 9

oh...hang on a sec I got it

Answer 10

\[\left(\begin{matrix}5 \\ 1\end{matrix}\right)=\left(\begin{matrix}5 \\ 4\end{matrix}\right)\]and,\[\left(\begin{matrix}5 \\ 2\end{matrix}\right)=\left(\begin{matrix}5 \\ 3\end{matrix}\right)\]These two give the same pairs of sets as you said :)

Answer 11

I've done combinations before and know them, but in this class we never actually reviewed them. Is there another way to do these problems?

Answer 12

The problem is basically to count a collection of objects. This is exactly what combinations (and permutations) deals with. To my mind, this is the math technique best suited for this problem. I can't think of another efficient way off the top of my head. There might be some special relation in set theory that makes sense of this (I never studied set theory formally) but I'm not aware of it.

Answer 13

Thanks!

Answer 14

No problem. If I think of another way I'll post it. Interesting problem... :)

Answer 15

Sounds good

Answer 16

Yeah, the only thing I can come up with is your course probably just expects you to list all the possible subsets and count them up. 15 is a reasonable number for you to do this (I guess), but the method of combinations is far superior, especially for lazy guys like me :)