# Finding the number of subset pairs of a set

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

-

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.

-
Knowing 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... –  rschwieb Oct 19 '12 at 17:06
So would it just be $3^n$? –  user26069 Oct 19 '12 at 17:15
@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$ –  Ross Millikan Oct 19 '12 at 17:18
@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. –  Ross Millikan Oct 19 '12 at 17:19
@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$. –  Hagen von Eitzen Oct 19 '12 at 17:33

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

-

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

-
It would help if you offered some reasoning. –  Chris Godsil Aug 29 '13 at 1:16
Please look at oeis.org/A000392 –  HEKTO Oct 19 '13 at 17:33

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.

-