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

  • 2
    $\begingroup$ It's a great question. Do you have any thoughts on it? $\endgroup$ – pjs36 Sep 28 '15 at 16:22
  • 3
    $\begingroup$ Are the inclusions strict? $\endgroup$ – 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)$,


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

Hence, the answer is $n!$

  • $\begingroup$ Why we need to consider A0= empty set? $\endgroup$ – guanyu ma Sep 28 '15 at 19:02
  • $\begingroup$ 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$ $\endgroup$ – user265328 Sep 29 '15 at 5:57

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.