Union of subsets
Let http://alt2.artofproblemsolving.com/...3eae45b689.gif be a set with http://alt1.artofproblemsolving.com/...4b047a603d.gif elements. In how many different ways can one select two not necessarily distinct or disjoint subsets of http://alt2.artofproblemsolving.com/...3eae45b689.gif so that the union of the two subsets is http://alt2.artofproblemsolving.com/...3eae45b689.gif? The order of selection does not matter. For example, the pair of subsets http://alt2.artofproblemsolving.com/...44985a1495.gif represents the same selection as the pair http://alt1.artofproblemsolving.com/...846834bc7c.gif
Firstly what does "two not necessarily distinct or disjoint subsets" mean?
And I've tried experimenting a bit. I wrote down the 16 different subsets for http://alt2.artofproblemsolving.com/...32db70e8c4.gif. There seems to be some pattern but I don't think brute force like this is the way to go...
So can someone explain an easier method? (Please don't leave out any steps cause I'm a beginner at combinatorics http://www.artofproblemsolving.com/F...les/tongue.gif)
Once again, I must ask: Don't you have a textbook or lecture notes?
Originally Posted by usagi_killer
Two sets A and B are not necessarily disjoint if their intersection does not necessarily equal to the empty set. And a group of integers in a set S do not necessarily have distinct subset sums if the set does not necessarily have distinct elements.
No, I'm not in university yet, I'm just self-learning because I am on holidays. The book doesn't really go into detail.
Originally Posted by Plato