2 ?

Awesome q2a theme

0 votes

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)

1. 2^n

2. 3^n

3.n^2

4.C(n , 2)

+7 votes

Best answer

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.

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.

8,437 questions

2,714 answers

13,238 comments

95,460 users