Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 ?

share|cite|improve this question
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
up vote 3 down vote accepted

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

share|cite|improve this answer

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.

share|cite|improve this answer
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 – DeepSea May 7 '14 at 6:52
Thanks for your help :) – square_one May 7 '14 at 6:59

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.