Dark Mode

5,776 views

15 votes

Let $S$ be a set of 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 ___________

edited
Mar 6, 2021
by Shiva Sagar Rao

Generalised formula was asked in TIFR2010-A-18

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

6

31 votes

Best answer

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$

2 votes

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$

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$