in Combinatory retagged ago by
5,776 views
15 votes
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 ___________
in Combinatory retagged ago by
by
5.8k views

2 Comments

$3^{10}$
2
2
edited by

Generalised formula was asked in TIFR2010-A-18

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

6
6

5 Answers

31 votes
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$

selected by
8 votes
8 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 Comments

ii. Belongs to A but not B

In (ii), it should be :

Does not belong to A but belongs to B.

4
4
Sir, can you plzz explain why not it doesn’t belong to A but belongs to B?
0
0
7 votes
7 votes

I have followed step by step derivation

I hope this helps

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

1 comment

i followed the same approach but was lenghty!
0
0
Answer:

Related questions