1
$\begingroup$

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 ?

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – David
    May 7, 2014 at 6:29
  • 2
    $\begingroup$ 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\})$. $\endgroup$
    – David
    May 7, 2014 at 6:32

2 Answers 2

Reset to default
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I interpret the following: \binom{n}{0}+\binom{n}{1}+\binom{n}{2}+...+\binom{n}{k}+...\binom{n}{n}=2^n $\endgroup$
    – square_one
    May 7, 2014 at 6:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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