Why is the cardinality of set S is 3^n, where S is the collection of all ordered pairs of disjoint subset of {1,2,3,...,n} where n is non negative. Why is the cardinality of set S is 3^n, where S is the collection of all ordered pairs of disjoint subset of {1,2,3,...,n} where n is non negative.
if n = 2, then subset A and B are disjoint and can only contain elements of 1,2, or the empty set, is this correct? I can't get 9 ordered pair. Can someone explain how do I get 9 ordered pair?
 A: Think of there being $3$ sets:  Set $A$, set $B$, and set $C$.  for each element $s\in \{1, \cdots, n\}$ you have three choices as to where to put it. Here the subset $C$ contains all the elements that are in neither set $A$ nor set $B$. As there are $n$ elements, that makes for $3^n$ total choices.
For $n=2$, the $9$ choices are $$(A,A),\, (A,B), \,(A,C),\,(B,A), \,(B,B), \,(B, C),\,(C,A), \,(C,B), \,(C,C)$$.
Just to clarify things, the choice $(B,C)$, to pick a random one, means that element $1$ is in the second set and element $2$ is in neither the first nor the second.  Thus it corresponds to the two disjoint sets $\emptyset, \{1\}$.
A: Here's an alternative proof, using induction.
For $n=0$ the case is easy: there is only one pair of disjoint subsets of $\varnothing$, namely $(\varnothing,\varnothing)$.
Suppose that there are $3^n$ pairs of disjoint subsets of $\{1,\dots,n\}$. For each pair of disjoint sets $(A,B)$, where both $A,B\subseteq\{1,\dots,n\}$ we can make three different pairs of disjoint subsets of $\{1,\dots,n,n+1\}$, namely $(A,B)$, $(A\cup\{n+1\},B)$ and $(A,B\cup\{n+1\})$. I'll leave it to you to show that this gives unique sets for every $(A,B)$. Hence the number of pairs of disjoint subsets of $\{1,\dots,n,n+1\}$ is three times the number of pairs of disjoint subsets of $\{1,\dots,n\}$, which is $3\cdot 3^n=3^{n+1}$ by induction hypothesis.
