GATE CSE 2021 | Set 2 | Question: 50

Question

Let $S$ be a set consisting of $10$ elements. The number of tuples of the form $(A,B)$ such that $A$ and $B$ are subsets of $S$, and $A \subseteq B$ is ___________

Comments

Similar Question: Combinatory: ISI2024-MCS-PCA | Question: 12

---

Let’s consider each element of S independently. For any element x∈S, it can be:

• In neither A nor B

• In B but not in A

• In both A and B

So each element has 3 choices that satisfy A⊆B.

---

10c0(1)+10c1(2) +10c2(2^2) +10c3(2^3)+........+10c10(2^10)
 

choose for b then for a

summation 10ck(2^k) from i=0 to 10;
ie binomial (1+2)^10=3^10

Answer 1

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

So, for the given question, answer will be $3^{10} = 59049$

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 ${}^nC_1$ 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 ${}^nC_1 \times 2^{n-1}$ 

When $|A| = 2$, there are ${}^nC_2$ 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 ${}^nC_2 \times 2^{n-2}$ 

and so on,

When $|A| = n$, there are ${}^nC_n = 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 ${}^nC_n \times 2^0$ 

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

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

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

So, for the given question, answer will be $3^{10} = 59049$

Comments

wow!

---

I tried to solve and understand this problem last year but did not get it. This year i learned Combinatorics from Deepak Poonia and came up with the solution myself and also understood the variations.. Thank you sir.

---

This is called "best answer" !!

Answer 2

I have followed step by step derivation

I hope this helps

Comments

your explantion is best .

---

Great explanation!!!

---

@shashankrustagi but there are repeatitions for (fi,fi)

Answer 3

every element in S have 3 choices.

i. Belongs to A and B

ii. Does not Belongs to A but belongs to B

iii. neither belongs to A nor B

 

10 elements, So 3$^{10}$ tuples can be possible.

Comments

since A is subset of B , every element of A belongs to B as well.

Therefore, this line is wrong : belongs to A but not B

---

Similar question with increased complexity

https://gateoverflow.in/426510/gate-mechanical-2024-ga-question-7

---

Best Answer !!

Answer 4

easiest method 

Answer 5

Suppose you’ve a set with elements = {A , B , C }

Then it’s power set P(S) will be = {$\phi$ , {A} , {B} , {C} , {A,B} , {B,C} , {A,C} , {A,B,C} }

Now taking the relation (A,B) , such that A $\subseteq$ B , it will have tuples of following kind :

({A}, {A,B})

For this particular tuple we can take any single element from the set , and form the power set with remaining elements and all those subsets will form the above such tuples with our chosen element.

And also, relation is not proper subset so $\phi$ can be treated as ({A},{A}) tuple

For ex : if we've chosen {a}, then remaining elements will be {b, c}.  P(s) of these will be {$\phi$, {b} , {c}, {b, c}} , and these will form the following tuples

{ ({a}, {a}) , ({a}, {a, b}) ,  ({a}, {a, c}), ({a}, {a, b, c}) }

Therefore for 3 element set answer will be :

$2^{3}$($\phi$ forming relation with each subset)

$+\binom{3}{1}2^{2}$(Choosing one element out of three and forming power set with remaining elements)

$+\binom{3}{2}2^{1}$(Choosing two element out of three and forming power set with remaining elements)

$+\binom{3}{3}2^{0}$(Choosing thre element out of three and forming power set with remaining elements)

 

Similar logic can be applied in the above question :

$2^{10}+\binom{10}{1}2^{9}+\binom{10}{2}2^{8}+\binom{10}{3}2^{7}+\binom{10}{4}2^{6}+\binom{10}{5}2^{5}+\binom{10}{6}2^{4}+\binom{10}{7}2^{3}+\binom{10}{8}2^{2}+\binom{10}{9}2^{1}+1 = (1+2)^{10}$

Answer : $3^{10}=59,049$

Comments

i followed the same approach but was lenghty!

Answer 6

Answer:- $3^{10}$

We’ll be using binary indicators to solve this problem.

Let 0- indicate the presence in the set; 1- indicate absence from the set.

We’ll be using a tuple of 2 indicator variables corresponding to 2 sets (A,B) for each element in S, each indicator will tell us whether that element is present or absent in set A & B respectively.

Listing down are valid combinations of the indicators satisfying the given constraint $A\subseteq B$:-

$A$	$B$
0	0
0	1
1	1

Note:-$(A,B)=(1,0)$ is an invalid combination as it’s not possible for an element to be present in A & not in B.

Now, it’s evident that there’re 3 choices for each element in $S$, making the ans  $3^{|S|}\ or\ 3^{10}$

Let’s try to generalize it to$(A_{1},A_{2},....A_{k}),where\ A_{i}\subseteq A_{i+1}\ \forall i, i<k, and\ A_{k}\subseteq S$, $|S|=n$

Initially all indicators are set to 0, or the indicator tuple looks like $(0,0,…….k\ times)$

$i=1$, If we set $A_{k}=1$ we get a valid tuple, similarly

$i=2$, if $A_{k-1}\&\&A_{k}==1$, or both $A_{k}\&A_{k-1}$ are set, we get a valid tuple, and so on:-

In $i^{th}$ step we’re setting last i indicators, till all the indicators are 1 when i=k

As this process iterates $k$ times, we get $k$ valid combinations, another valid combination is our initial setup when all k indicators are 0, or the element of $S$ is present in none of the subsets $A_{i}$.

So, in total we’ve $(k+1)$ valid bit combinations for every element in $S$.

Or, $(k+1)^{|S|}=(k+1)^{n}$  valid tuples of the given form.