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.

  • $\begingroup$ 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. $\endgroup$ – vadim123 Jan 27 '16 at 18:30
  • $\begingroup$ @vadim123 I dont get what you mean $\endgroup$ – Zero Jan 27 '16 at 18:45
  • $\begingroup$ If $A_1-A_0$ contains no elements, then $A_1=A_0$, so they are not distinct. $\endgroup$ – vadim123 Jan 27 '16 at 18:46
  • $\begingroup$ @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 $\endgroup$ – Zero Jan 27 '16 at 18:56
  • $\begingroup$ Weird is sometimes right. :-) $\endgroup$ – 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.

  • $\begingroup$ so wouldnt that make the answer n! @Unit $\endgroup$ – Zero Jan 27 '16 at 19:00
  • $\begingroup$ Yes, because we end with $n-(n-1)$ choices for $A_n$. $\endgroup$ – Unit Jan 27 '16 at 19:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.