TIFR CSE 2010 | Part A | Question: 18

Question

Let $X$ be a set of size $n$. How many pairs of sets (A, B) are there that satisfy the condition $A\subseteq B \subseteq X$ ?

• A. $2^{n+1}$
• B. $2^{2n}$
• C. $3^{n}$
• D. $2^{n} + 1$
• E. $3^{n + 1}$

Comments

Another way to prove it.

---

smsubham why would you screenshot a comment of someone else? which is under the same question?

---

Application of this question was asked in GATE CSE 2021 Set 2 | Question: 50

Similar questions: TIFR2012-A-8, GATE CSE 2003 | Question: 5

Answer 1

Option $C$ i.e. $3^{n}$must be the right answer.

It is given that there are $n$ elements in the set $X$.

Consider an element $p$ of set $X$.

What are the choices it will have?

1. Either it can be present in set $A$ & set $B$ both.
2. Or it can absent from set $A$ & present in set $B$.
3. Or it can be absent from both set $A$ & set $B.$

But since it is given that $A$ must be a subset of $B$, it is not possible that it can be present in $A$ & absent from $B$.

So, it each of the n elements of set $X$ have $3$ choices available.

So, total choices available for formation of sets $A$ & $B$ $=$ $3^{n}$, which will give $3^{n}$ such different $(A, B)$ pairs.

Comments

Good Logic. Absolutely perfect.

---

In case set A is not the subset of set B , would the answer be = 4ⁿ?

---

yes...then evry elemnt would have four chance...wither ir goes to A or B or Both or None....

therefor it would be 4ⁿ,...

---

Another way to prove this - 
Let's fix B and find the number of satisfying sets A(i.e subsets of B ).
 If $|B|=k$, then there are $2^k$ possible choices for A.

Now let's sum over all choices of B.
For each k, there are $\binom{n}{k}$ choices for B, each with 2^k choices for A, giving $\sum_{k=0}^{n}\binom{n}{k}.2^{k}$ .

Notice that if we rewrite it as $\sum_{k=0}^{n}\binom{n}{k}.2^{k}.1^{n-k}$  then this is exactly the binomial expansion of $(1+2)^n = 3^n$

Answer 2

Total number of subsets of  a set of size of n = ⁿC₀ + ⁿC₁ + ....... + ⁿC_n

Total number of subsets of size k (0<=k<=n) = ⁿC_k

Total number of (A,B) pairs such that |B| is equal to k = all possible subsets of B * total number of subsets of size k

                                                                                       = 2^k * ⁿC_k = ⁿC_k*2^k

Total number of (A,B) pairs = ⁿC₀  2⁰+ ⁿC₁ 2¹ + ....... + ⁿC_n 2ⁿ = 3ⁿ

          

Comments

Just for Extra information ->

This series is actually

(1+2)^n ! Try to expand it using binomal theorem, you will get expression->

ⁿC₀  2⁰+ ⁿC₁ 2¹ + ....... + ⁿC_n 2ⁿ = 3ⁿ

Answer 3

We want the ordered pairs $(A,B)$ where $(A \subseteq S , B \subseteq S ; A \subseteq B ;)$

Let’s find general solution i.e. when $|S| = n$

Method 1 :

We want the ordered pairs $(A,B)$ where $(A \subseteq S , B \subseteq S ; A \subseteq B ;)$

For every element $x$ of set $S, $ we have three choices :

Choice 1 : $x \notin A \,\, and  \,\,x \notin B$

Choice 2 : $x \notin A \,\, and  \,\,x \in B$

Choice 3 : $x \in A \,\, and  \,\,x \in B$

So, for each element we have 3 choices, and we have $n$ elements , so, answer will be $3^n.$

NOTE : This method is nice and can be used to solve a wide variety of problems/variations very easily and in less time. 

For example, Try the following variations :

Variation 1 : Find the number of ordered triples $(A,B,C)$ where $(A,B,C \subseteq S ; A \subseteq B \subseteq C ;)$

Answer : For every element $x$ of set $S, $ we have 4 choices. So, $4^n$

Variation 2 : Find the number of ordered triples $(A,B,C)$ where $(A,B,C \subseteq S ; A \subseteq B \supseteq C ;)$

Answer : For every element $x$ of set $S, $ we have 5 choices. So, $5^n$

Variation 3 : Find the number of ordered triples $(A,B,C)$ where $(A,B,C \subseteq S ; A \subseteq B ; A \subseteq C ;)$

Answer : For every element $x$ of set $S, $ we have 5 choices. So, $5^n$

Variation 4 : Find the number of ordered triples $(A,B)$ where $(A,B \subseteq S ; A \cap B = \phi )$

Answer : For every element $x$ of set $S, $ we have 3 choices. So, $3^n$

Many more questions can be easily solved by this method, so it is good to practice it. 

---

Method 2 :

If we make ordered pairs $(A,B)$ where $(A \subseteq S , B \subseteq S ; A \subseteq B ;)$ such that $A$ has $k$ elements in it then for $B$ we have $2^{(n-k)}$ possible choices.  (Because those $k$ elemetns of $A$ must in present in $B$ so there is no choice for them But for each of the remaining $n-k$ elements of $S,$ we have 2 choices for each element)

For example, if $A = \{ a1,a2 \}$ then how many supersets are possible for $A ?$ 

There will be $2^{n-2}$ supersets of $A.$

So the number of ordered pairs $(A,B)$ where $(A \subseteq S , B \subseteq S ; A \subseteq B ;)$ that we have :

We can divide it into cases : 

When $|A| = 0 $ OR $|A| = 1$ OR $|A| = 2$ OR $\dots $ $|A| = n$

When $|A| = 0$, there is only one such $A$ is possible, that is $A = \phi$, So, number of possible $B's = 2^n ; $ So total $(A,B)$ pairs in this case will be $1 \times 2^n$ 

When $|A| = 1$, there are $nC1$ such $A$ possible, So, for each possible $A$, the number of possible $B's = 2^{n-1} ; $ So total $(A,B)$ pairs in this case will be $nC1 \times 2^{n-1}$ 

When $|A| = 2$, there are $nC2$ such $A$ possible, So, for each possible $A$, the number of possible $B's = 2^{n-2} ; $ So total $(A,B)$ pairs in this case will be $nC2 \times 2^{n-2}$ 

and so on,

When $|A| = n$, there are $nCn = 1$ such $A$ possible, So, for each possible $A$, the number of possible $B's = 2^{n-n} = 2^0 ; $ So total $(A,B)$ pairs in this case will be $nCn \times 2^0$ 

We want total possible pairs $(A,B)$ so we can add all the above cases :

$nC0 \times 2^n$ + $nC1 \times 2^{n-1}$ + $nC2 \times 2^{n-2}$ + $\dots$ $nCn \times 2^0$

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

---

 

Comments

Amazing ! As always Sir🙏

---

Those variations made look the original problems’ solution as cherry on top. Amazing explanation Sir.

Answer 4

Simple way to answer it using example.
Answer is 3^n

Lets say X={1,2}  hence  n=2

1) {1} ⊆ {1} ⊆ {1,2}

2) {2} ⊆ {2} ⊆ {1,2}

3) {1} ⊆ {1,2} ⊆ {1,2}

4) {2} ⊆ {1,2} ⊆ {1,2}

5) {1,2} ⊆ {1,2} ⊆ {1,2}

I was confused,  I thought it is 2^n +1   ..
Then I knew, I have not included these   :)

6) {} ⊆ {} ⊆ {1,2}

7) {} ⊆ {1} ⊆ {1,2}

8) {} ⊆ {2} ⊆ {1,2}

9) {} ⊆ {1,2} ⊆ {1,2}   

So  3^2 =9

Comments

Thank you very much for the proof the last part was where I was confused as well