Combinatorial reasoning question

Count the ways to choose distinct subsets $A_0, A_1, \ldots , A_n$ of $\{1, 2, . . . , n\}$ such that $A_0 \subset A_1 \subset \ldots \subset A_n$.

• It's a great question. Do you have any thoughts on it? – pjs36 Sep 28 '15 at 16:22
• Are the inclusions strict? – ajotatxe Sep 28 '15 at 16:25

Assuming that the inclusion is strict, the answer is $n!$.

Since you need to choose $n+1$ strictly increasing sets from a set of cardinality $n$, $A_0$ must be $\phi$ and $A_i$ must contain exactly $i$ elements. So, the number of ways of choosing:

$A_1 = n$,

$A_2 = (n-1)$,

$\vdots$

$A_n = 1$ ($A_n$ must be $\{1,2, \dots , n\}$)

Hence, the answer is $n!$

• Why we need to consider A0= empty set? – guanyu ma Sep 28 '15 at 19:02
• For the sake of simplicity, take $n=2$. The set becomes $\{1,2\}$. Now you need sets $A_0, A_1, A_2$ such that $A_0 \subset A_1 \subset A_2$. Suppose $A_0 = \{1\}$ then $A_1$ must contain 1 element more than $A_0 \implies A_1 = \{1,2\}$. So there is no choice left for $A_2$ – user265328 Sep 29 '15 at 5:57