# 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 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.

• There's a problem, you are not forcing the $A_i$ to be distinct. To do this, you also need each of $A_1-A_0, \ldots, A_n-A_{n-1}$ to be nonempty. But there are $n$ of these, and $n$ elements. Hence each contains exactly one element, and $A_0$ must be empty. – vadim123 Jan 27 '16 at 18:30
• @vadim123 I dont get what you mean – Zero Jan 27 '16 at 18:45
• If $A_1-A_0$ contains no elements, then $A_1=A_0$, so they are not distinct. – vadim123 Jan 27 '16 at 18:46
• @vadim123 so the final answer is wrong? Because if you apply whart you are saying then in closed form the answer should be n! i think which seems weird – Zero Jan 27 '16 at 18:56
• Weird is sometimes right. :-) – vadim123 Jan 27 '16 at 19:38

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.
• Yes, because we end with $n-(n-1)$ choices for $A_n$. – Unit Jan 27 '16 at 19:04