in Combinatory recategorized by
4,709 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 recategorized by
by
4.7k views

2 Comments

$3^{10}$
1
1
edited by

Generalised formula was asked in TIFR2010-A-18

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

6
6

Subscribe to GO Classes for GATE CSE 2022

5 Answers

20 votes
20 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.

3
3
Sir, can you plzz explain why not it doesn’t belong to A but belongs to B?
0
0
5 votes
5 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
1 vote
1 vote

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.

 

 

Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true