45 views
Suppose that S is a set with n elements. How many ordered pairs (A , B) are there such that A and B are subsets of S and A is subset of B?

1. 2^n

2. 3^n

3.n^2

4.C(n , 2)
| 45 views
0
2 ?
0
yes correct option is 2

If we have a set containing $n$ elements and we want to make any subset of this set, then we have two choices for each of the elements i.e, we can either include the element or not include the element in our subset, hence total number of possible subsets will be $2^n$.

Now, we want $A$ and $B$ to be subsets of $S$, and we also want $A$ to be a subset of $B$.

In other words, $B$ must be a subset of $S$ and $A$ must be a subset of $B$.

If we consider that $B$ is a subset of $S$, containing exactly $i$ elements, then we can choose any $i$ of the available $n$ elements from $S$ to be included in $B$, hence, there are total $^nC_i$ possible subsets which will have exactly $i$ elements.

Now, $B$ contains $i$ elements, hence total number of possible subsets of $B$ will be $2^i$ (as mentioned in the beginning of answer).

Hence, we have $^nC_i$ possibilities for $B$ (containing $i$ elements), and for each of these, we have $2^i$ possible subsets, which are the possibilities for $A$.

$\implies$ We have $^nC_i*2^i$ possible ordered pairs $(A,B)$ where $B$ contains exactly $i$ elements and $A$ is a subset of $B$.

Now, we know that $B$ can contain $0$ to $n$ number of elements, hence total number required ordered pairs will be:

$\sum_{i=0}^{i=n}$  $^nC_i*2^i$

$=\ ^nC_0*2^0 +\ ^nC_1*2^1 +\ ^nC_2*2^2 +\dots +\ ^nC_n*2^n$

$=\ ^nC_0*2^0*1^{n-0} +\ ^nC_1*2^1*1^{n-1} +\ ^nC_2*2^2*1^{n-2} +\dots +\ ^nC_n*2^n*1^{n-n}$

This is binomial expansion of $(2+1)^n = 3^n$.

Hence, option $2$ is the correct answer.
by (855 points)
selected
+1

one more way is :

every element of S, can have 3 possibilities :

1. present in A and B
2. present in B but not A
3. neither present in A nor in B

There are n elements, So it is 3$^n$

0
Great, this is the best way!