retagged by
11,775 views
25 votes
25 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 ___________
retagged by

6 Answers

Best answer
59 votes
59 votes

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$

selected by
13 votes
13 votes
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.
edited by
2 votes
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$
edited by
Answer:

Related questions

8 votes
8 votes
1 answer
3
Arjun asked Feb 18, 2021
6,463 views
Consider the following augmented grammar with $\{ \#, @, <, >, a, b, c \}$ as the set of terminals. $$\begin{array}{l} S’ \rightarrow S \\ S \rightarrow S \# cS \\ S \r...
24 votes
24 votes
3 answers
4