# Count of Disjoint subsets

Let $A$ be a set of $n$ elements. The number of ways, we can choose an ordered pair $(B, C)$, where $B$, $C$ are disjoint subsets of $A$, equals

(A) $n^2$ (B) $n^3$ (C) $2^n$ (D) $3^n$

Doubt 1: What is a disjoint subset ?

My Attempt at the above problem: Assume 5 elements. Ordered pairs would be: $$(1,1),(1,2),(1,3),(1,4),(1,5),(2,1),(2,2),(2,3),(2,4),(2,5),(3,1),(3,2),(3,3),(3,4),(3,5),(4,1),(4,2),(4,3),(4,4),(4,5),(5,1),(5,2),(5,3),(5,4),(5,5)$$

25 elements. So, the answer would be: (A) $n^2$.

Is this the right approach ? Any better ways to solve this ?

• There is no such thing as "a disjoint subset". Two subsets are disjoint if they have no element in common, that is, their intersection is empty. May 7, 2014 at 6:29
• Read your question more carefully! The items you have listed are ordered pairs $(b,c)$ where $b,c$ are elements of $A$. You are asked for ordered pairs of subsets of $A$, for example, $(\{1,4\},\{2,5\})$. May 7, 2014 at 6:32

Take each of the $n$ elements of $A$ one by one and decide whether to put it in $B$ or in $C$. No element can go in both $B$ and $C$ because they are supposed to be disjoint, so there are three options: in $B$, or in $C$, or neither. The total number of pairs is $3^n$.
Assume $B \cup C = A$. Then if $B$ has $k$ element, then there are $\binom{n}{k}$ ways. Thus the total number of ways to do this is: $2^n$ because you get the sum of all these $\binom{n}{k}$'s for $k$ runs from $0$ to $n$. It is choice $C$
If $B \cup C \subseteq A$, then there are more cases and the answer should be $3^n$. The question isn't absolutely clear.