recategorized by
1,355 views

3 Answers

3 votes
3 votes
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}$
edited by
0 votes
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$
0 votes
0 votes

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$

Related questions

1 votes
1 votes
2 answers
1
Arjun asked Sep 23, 2019
776 views
A set contains $2n+1$ elements. The number of subsets of the set which contain at most $n$ elements is$2^n$$2^{n+1}$$2^{n-1}$$2^{2n}$
2 votes
2 votes
2 answers
2
Arjun asked Sep 23, 2019
1,024 views
Let $X$ be the set $\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10 \}$. Define the set $\mathcal{R}$ by $\mathcal{R} = \{(x,y) \in X \times X : x$ and $y$ have the same remainder when d...
0 votes
0 votes
1 answer
4
Arjun asked Sep 23, 2019
517 views
Consider the sets defined by the real solutions of the inequalities$$A = \{(x,y):x^2+y^4 \leq 1 \} \:\:\:\:\:\:\:\: B = \{ (x,y):x^4+y^6 \leq 1\}$$Then$B \subseteq A$$A \...