# 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. –  David May 7 '14 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\})$. –  David May 7 '14 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.

-
I interpret the following: \binom{n}{0}+\binom{n}{1}+\binom{n}{2}+...+\binom{n}{k}+...\binom{n}{n}=2^n –  square_one May 7 '14 at 6:50
@user148176: true –  Back2Basic May 7 '14 at 6:52
Thanks for your help :) –  square_one May 7 '14 at 6:59