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

Question

I was given this question. Count the ways to choose distinct subsets $A_0, A_1, . . . , A_n$ of ${1, 2, . . . , n}$ such that $A_0 ⊂ A_1 ⊂ . . . ⊂ A_n$

I followed a different example to solve this

Let us count the number of ways to assigning elements to $A_0; A_1 - A_0; A_2 - A_1, ..... , A_n - A_n-1$, and X. Now, however, there are no constraints, so each of the n elements can choose any of the n + 2 sets, which gives $(n+2)^n$

Is my solution correct? It seems to me like i feel as if it is unfinished or it could be more detailed.

Answer 1

From the strict inclusions we can get the size of each set in a chain: $|A_i| \ge |A_{i-1}| + 1$, so $|A_n| \ge n + |A_0|$. On the other hand, $A_n \subseteq \{1, \dotsc, n\}$! This forces $|A_i| = i$.

In particular, $A_0$ is empty, there are $n$ choices for $A_1$, and $n-1$ choices for $A_2$ given $A_1$, and so on.