# 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