+1 vote
33 views

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

1. $n^2$
2. $n^3$
3. $2^n$
4. $3^n$

recategorized | 33 views

+1 vote
If we choose k elements from a set A of n elements and put it in set B ,then from the remaining n-k elements in A we can select 0 to n-k elements and put it in C. These 2 sets B,C are disjoint.

For example,A={1,2,3,4,5,6} then if B={1,6,3,5} then remaining elements in A ={2,4}.Now C can be {},{2},{3},{2,3}.These B,C form disjoint subsets.

here k ranges from 0 to n.

And l ranges from 0 to n-k.

Therefore number of ordered pairs=$\sum_{k=0}^{k=n}\left ( \binom{n}{k}*\sum_{l=0}^{l=n-k}\binom{n-k}{l}\right )$

Now,$\sum_{l=0}^{l=n-k}\binom{n-k}{j}=(1+1)^{n-k}$$=2 ^{n-k}$

=$\sum_{k=0}^{k=n}\binom{n}{k}*2^{n-k}$

=$(1+2)^{n}$

=$3^{n}$
by Active (3.1k points)
edited
+1
BTW why did you think $\mathrm{B} \cup \mathrm{C} =\mathrm{A}$ always?

The question just said $\mathrm{B} \subseteq \mathrm{A}$, $\mathrm{C} \subseteq \mathrm{A}$ and $\mathrm{B} \cap \mathrm{C}=\varnothing$.
+1
Thanks for pointing it out. Before solving this question, i solved a partition based question in equivalence relations and i was thinking in same manner.. Let me check and update it.

By the way nice observation...

P.s: edited now
Lets say we have a set of 5 elements then the number of disjoint subsets of $A$ can be formed as

$\text{(0, 5), (1, 4), (2, 3), (3, 2), (4, 1), (5, 0)}$

So total possibilities

= $5 \choose 0$* $5 \choose 5$ + $5 \choose 1$* $4 \choose 4$ +$5 \choose 2$* $3 \choose 3$ + $5 \choose 3$* $2 \choose 2$+ $5 \choose 4$* $1 \choose 1$ + $5 \choose 5$* $5 \choose 0$

$= \text{1*1 + 5*1 + 10*1 + 10 *1 + 5*1 + 1}$

$= 32 \\ =2^5$

Hence answer is option $C$
by Active (2.2k points)