ISI2021-MMA: 7

Question

Let $S$ be a set of $n$ elements. The number of ways in which $n$ distinct non-empty subsets $X_{1}, \dots, X_{n}$ of $S$ can be chosen such that $X_{1} \subseteq X_{2} \dots \subseteq X_{n},$ is

• A. $\left( \begin{array} c n \\ 1 \end{array} \right) \left( \begin{array} c n \\ 2 \end{array} \right) \dots \left( \begin{array} c n \\ n \end{array} \right)$
• B. $1$
• C. $n!$
• D. $2^{n}$

Answer 1

Method 1:-

This method we can do in exam by taking small example .

$S=\left \{ 1,2,3 \right \}$ is a set of $3$ element . So $n=3$ .

Now, non empty subsets of S are,

$\left \{ 1 \right \}$,$\left \{ 2 \right \}$,$\left \{ 3 \right \}$,$\left \{ 1,2 \right \}$,$\left \{ 1,3 \right \}$,$\left \{ 2,3 \right \}$,$\left \{ 1,2,3 \right \}$

Now we have to choose n=3 distinct subsets such that $X_{1}\subseteq X_{2}\subseteq X_{3}$ .

Possible choices are :-

$\left \{ 1 \right \}\subseteq \left \{ 1,2 \right \}\subseteq \left \{ 1,2,3 \right \}$

$\left \{ 1 \right \}\subseteq \left \{ 1,3 \right \}\subseteq \left \{ 1,2,3 \right \}$

$\left \{ 2 \right \}\subseteq \left \{ 2,3 \right \}\subseteq \left \{ 1,2,3 \right \}$

$\left \{ 2 \right \}\subseteq \left \{ 1,2 \right \}\subseteq \left \{ 1,2,3 \right \}$

$\left \{ 3 \right \}\subseteq \left \{ 1,3 \right \}\subseteq \left \{ 1,2,3 \right \}$

$\left \{ 3 \right \}\subseteq \left \{ 2,3 \right \}\subseteq \left \{ 1,2,3 \right \}$

So total 6 possible ways are there for $n=3$.

Now if put n=3 is option only Option C gives $6$ answer.

So Correct answer is $n!$

This approach we can employ in exam .

---

Method 2:-

Let $S=\left \{ a_{1},a_{2},a_{3},....,a_{n} \right \}$

Here we have to select $n$ distinct non empty subsets of S such that $X_{1}\subseteq X_{2}\subseteq X_{3}\subseteq .......\subseteq X_{n}$

Now as $n$ subsets we choose are distinct and has to maintain the given condition, The cardinality of  $|X_{i}|=i$ for all $i$ from 1 to n.

So $X_{1}$ has only one element in it.

just take $X_{1}$=$\left \{ a_{1} \right \}$

Now for $X_{2}$ has to be a set with 2 element in it one of the element should $a_{1}$ as it needs to be a superset of $X_{1}$.

$X_{2}=\left \{ a_{1},?\right \}$

How many choices we have for $“?”$  ?

= Here we have $n-1$ choices to fill $“?”$ . 

Now similarly $X_{3}$ have $3$ elements in it.

Say $X_{2}=\left \{ a_{1},a_{3}\right \}$ .Now $X_{3}$ has to be a superset of $X_{2}$ . 

$X_{3}=\left \{ a_{1},a_{3},?\right \}$

How many choices we have for $“?”$  ?

=>  Here we have $n-2$ choices to fill $“?”$ . 

 

Now going in the similar way How many choice we have $X_{n}$ ?

=> $X_{n}$ always has to be the base set S which is of size $n$ . So we have $1$ choice for that.

So , by Choosing $X_{1}$=$\left \{ a_{1} \right \}$ we have total $(n-1)*(n-2)*(n-3)*....*2*1=(n-1)!$ ways to satisfy the given condition.

Now For  $X_{1}$ we have $n$ choices as $\left \{ a_{1} \right \}$,$\left \{ a_{2} \right \}$,$\left \{ a_{3} \right \}$,….$\left \{ a_{n} \right \}$.

So total number of ways are =$n*(n-1)!=n!$

Correct answer is (C) .

Comments

@Deepak Poonia sir is this explanation correct ?

---

Excellent answer, without a single flaw. Keep writing.

---

@Deepak Poonia thank you sir .

---

nicely explained