The Gateway to Computer Science Excellence
+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$
in Combinatory by Veteran (424k points)
recategorized by | 33 views

2 Answers

+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 by
+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
0 votes
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)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,648 questions
56,429 answers
195,207 comments
99,916 users