3
$\begingroup$

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$?

5 Answers 5

6

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.

  • 0
    @rschwieb: I deleted that comment2012-10-19
1

Number of different pairs of non-empty disjoint subsets of a set with n elements is:
(3n - 2n + 1 + 1) / 2.

  • 0
    Please look at http://oeis.org/A0003922013-10-19
1

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.

1

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.

  • 0
    You 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
0

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$.