Awesome q2a theme
0 votes
Suppose that S is a set with n elements. How many ordered pairs (A , B) are there such that A and B are subsets of S and A is subset of B?

1. 2^n

2. 3^n


4.C(n , 2)
in Set Theory & Algebra by (7 points) | 45 views
2 ?
yes correct option is 2

1 Answer

+7 votes
Best answer
If we have a set containing $n$ elements and we want to make any subset of this set, then we have two choices for each of the elements i.e, we can either include the element or not include the element in our subset, hence total number of possible subsets will be $2^n$.


Now, we want $A$ and $B$ to be subsets of $S$, and we also want $A$ to be a subset of $B$.

In other words, $B$ must be a subset of $S$ and $A$ must be a subset of $B$.


If we consider that $B$ is a subset of $S$, containing exactly $i$ elements, then we can choose any $i$ of the available $n$ elements from $S$ to be included in $B$, hence, there are total $^nC_i$ possible subsets which will have exactly $i$ elements.


Now, $B$ contains $i$ elements, hence total number of possible subsets of $B$ will be $2^i$ (as mentioned in the beginning of answer).


Hence, we have $^nC_i$ possibilities for $B$ (containing $i$ elements), and for each of these, we have $2^i$ possible subsets, which are the possibilities for $A$.

$\implies$ We have $^nC_i*2^i$ possible ordered pairs $(A,B)$ where $B$ contains exactly $i$ elements and $A$ is a subset of $B$.


Now, we know that $B$ can contain $0$ to $n$ number of elements, hence total number required ordered pairs will be:

$\sum_{i=0}^{i=n}$  $^nC_i*2^i$


$=\ ^nC_0*2^0 +\ ^nC_1*2^1 +\ ^nC_2*2^2 +\dots +\ ^nC_n*2^n$


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


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


Hence, option $2$ is the correct answer.
by (855 points)
selected by

one more way is :

every element of S, can have 3 possibilities :

  1. present in A and B
  2. present in B but not A
  3. neither present in A nor in B

There are n elements, So it is 3$^n$

Great, this is the best way!
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
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
8,437 questions
2,714 answers
95,460 users