ISI2015-MMA-8

Question

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$

Comments

Detailed Video Explanation with Complete Analysis: https://www.youtube.com/watch?v=Mxxzmd-BQ18&t=1807s

Same Question in ISI, TIFR:

• https://gateoverflow.in/432358/isi2024-mcs-pca-question-12 
• https://gateoverflow.in/21007/tifr-cse-2012-part-a-question-8 

Answer 1

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

Comments

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

---

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

---

Easy, Efficient Method to solve All such questions: https://www.youtube.com/watch?v=Mxxzmd-BQ18&t=1807s

Answer 2

Each element of $A$ has 3 choices :

1. It can be in set $B$
2. It can be in set $C$
3. It can be in neither set $B$ nor set $C$

so that makes  answer $(d)$ $3^n$

Comments

Your question means that you need to find the number of ways an ordered pair(B,C) can be selected such that B and C are subsets and B∩C=∅.

To do so we can reduce this problem into another simpler one. Let each element of A(which has say n elements) represent a different ball. So now you have n balls.

Let's take two boxes B and CC and a rubbish chute R(which will be of use when you don't want the element/ball in any of the set/box).

Now each of the n balls can go into either B, C or R. Which implies that each of the n ball can be used in three ways.

It means that the number of ways of using the balls is 3^n. The balls in B and C represent the different elements of subsets.

Therefore if we have a set A with n elements, there would exist 3^n ordered pair of disjoint subsets(B,C). 

Refrence 

https://math.stackexchange.com/questions/684683/number-of-ways-to-choose-two-disjoint-subsets-of-a-set

Answer 3

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$