If a set $S$ has $n$ elements, how many such pairs $(A,B)$ can be formed where $A$ and $B$ are subsets of $S$ and $A \cap B = \emptyset$?
Finding the number of subset pairs of a set
5 Answers
Hint: If you don't insist that $A \cup B = S$, each element has three places it can go: into $A$, into $B$ or neither.
-
0Knowing your answers, Ross, and seeing the upvotes, I'm convinced this is a good hint. But for the life of me I cannot see how it works :) I think I'm just not a combinatorics person... – 2012-10-19
-
1So would it just be $3^n$? – 2012-10-19
-
0@rschwieb: think about picking up each element of $S$ in turn and putting into one of three boxes. How many ways are there to do that? Then the ones you put into first box are $A$, the second $B$ – 2012-10-19
-
0@user46221: that's right. It is like the argument that the number of subsets of $S$ is $2^n$-each element can be in or out. – 2012-10-19
-
0@rschwieb: What do you mean "no matter what sets $A,B$ you chose"? It is the very task to count the *ways* to chose $A,B$, not count some number for possibly different choices of $A,B$. – 2012-10-19
-
0@RossMillikan I see now :) Thanks for the efficient explanation! – 2012-10-19
-
0@RossMillikan No, my answer does not suggest that you stop at just one $A$. The obvious implication is that you then have to sum over all $A$. *fix $A$ for a moment* I guess that suggestion leaves the worker grossly open to double counting though... Your answer is obviously the way to go. – 2012-10-19
-
0@rschwieb: I deleted that comment – 2012-10-19
Number of different pairs of non-empty disjoint subsets of a set with n elements is:
(3n - 2n + 1 + 1) / 2.
-
0It would help if you offered some reasoning. – 2013-08-29
-
0Please look at http://oeis.org/A000392 – 2013-10-19
There are (3n - 2n+1 + 1) / 2 such pairs of non-empty subsets.
We either put an element in A, in B or in the None bag. There are 3n possibilities to do that, but they include the cases where A or B is empty, the number of these cases has to be substracted from the result.
There are 2n cases where all of the elements were put in B and the None bag and A is empty, and similarly 2n cases where B is empty. Those 2 * 2n = 2n+1 cases has to be substracted from the result. There is one case though where everything went to None, that one case got substracted twice, so we only have to substract 2n+1 - 1.
Now we are at 3n - 2n+1 + 1 and have all possible pairs included twice as (x, y) and (y, x), so dividing by two gives the final result.
I doubt the answer above that states $\frac{(3^n-2^{n+1}+1)}{2}$. Consider $S = \{{1,2}\}$, $\{A,B\}$ might be $\{\{1\},\{1,2\}\}$ or $\{\{2\},\{1,2\}\}$. But the answer given by this formula for n=2 is 1.
If we consider the order of A and B but A and B may be duplicate sets, then the answer should be $$\sum_{i=1}^n {n\choose i}3^{n-i} = 4^n-3^n$$ This means to choose $i$ elements as intersection, then for the rest of elements, they have 3 choices: go into A, go into B and go into None. The situation when the order of A and B doesn't matter is similar to this one. Simply add one(when A and B are universal set) and divide it by 2.
If we do not allow duplicate sets but consider order, then the answer should be $$\sum_{i=1}^n {n\choose i}(3^{n-i}-1) = 4^n-3^n-2^n+1$$ If we do not consider order, then the answer would be a half of the expression above.
-
0You appear to have answered hastily, despite the 5+ year history of the Question, and overlooked the condition $A\cap B = \emptyset$. Perhaps a more relaxed pace in responding to older Questions is advantageous. – 2018-03-23
Hint:
If you consider fixed $A$ for a moment, then $B$ must be a subset of the complement of $A$, and so there are $2^{n-i}$ choices for $B$.