GATE CSE 1987 | Question: 9e

Question

How many true inclusion relations are there of the form $A \subseteq B$, where $A$ and $B$ are subsets of a set $S$ with $n$ elements?

Comments

Similar question: TIFR2010-A-18 - GATE Overflow

---

Just to make the question clearer, we need to find the number of ways of choosing a subset A, such that :- A ⊆ B ⊆ S.

Now, no. of ways in which B can be chosen from S = nC0+nC1+…+nCn=nC0+nC1+…+nCn

So, no. of ways in which A can be chosen from B =

nC0 * 2^0 + nC1 * 2^1 + nC2 * 2^2 + … + nCn * 2^n (since when we choose a subset B having k elements, then no. of subsets (for A) from those k elements will be 2^k).

---

Each element of set S has 3 choices→

(i) Either to be in set B and not in set A.

(ii) Be in both set A and B.

(iii) Neither in A nor in B.

Note that it is not possible for a element to be in set A and not in B. So 3^n is the answer

Answer 1

Number of subsets of a set of $n$ elements $ = 2^n$

$\quad = {}^nC_0 + {}^nC_1+\ldots + {}^nC_n$

Each of these terms ${}^nC_k$ denotes the number of possible subsets of size $k.$

Now given a subset of size $k,$ how many subsets can it have? $\implies 2^k.$

So, in this way number of inclusive relations on subsets of a set with $n$ elements

$\quad = 2^0 \times {}^nC_0 +2^1 \times {}^nC_1+\ldots +2^n \times {}^nC_n = 3^n$

PS: $3^n = (2+1)^n = {}^nC_0 \times2^0\times1^n + {}^nC_1\times 2^1 \times1^{n-1} \ldots {}^nC_n\times 2^n\times1^0$

Comments

@Arjun

You are calculating the size of the relation R = { (A,B) | A⊆B }. I think the question is asking for the number of subsets of R which is $2^{3^{n}}$. Please correct me if I am wrong.

---

Let’s take an example of {1,2}

Subsets: {Φ}, {1}, {2}, {1,2}

Now {1} & {2} are proper subsets of {1,2} =2

and {Φ} is a proper of subset of {1}, {2} and {1,2}

So accordingly, the answer should be 5 right? Please correct me if I’m wrong

---

The question is about a subset, not a proper subset.

$\phi$ is a subset of $\{1,2\},$ not $\{\phi\}$.

$\phi$ means $\{\}$ and $\{\phi\}$ means $\{\{\}\}$

For $S=\{1,2\}$ inclusion relations of the form $A \subseteq B$ will be:

$\phi \subseteq \{1\}$

$\phi \subseteq \{2\}$

$\phi \subseteq \{1,2\}$

$\{1\} \subseteq \{1,2\}$

$\{2\} \subseteq \{1,2\}$

$\{1,2\} \subseteq \{1,2\}$

$\{1\} \subseteq \{1\}$

$\{2\} \subseteq \{2\}$

$\phi \subseteq \phi$

Answer 2

There are 2^n true inclusion relations of the form A ⊆ B, where A and B are subsets of a set S with n elements.