Say that I have the set $[n] = \{1,2,...,n\}$ and a collection $\mathcal{C} = \{ S\_1, S\_2, ..., S\_k \}$ of subsets of $[n]$. Say that $\mathcal{C}$ is *valid* if it is closed under the superset operation; i.e., if $(S \in \mathcal{C} \wedge S \subseteq S' \subseteq [n]) \implies S' \in \mathcal{C}$. How many valid collections $\mathcal{C}$ are there, as a function of $n$?


Without the requirement to be closed under superset, the question is easier. There are $2^n$ subsets of $[n]$, and so there are $2^{2^n}$ ways to choose which of them belong to the collection. But not all collections are valid; for instance, if $n=2$, the valid collections are


$\mathcal{C} = \{ \emptyset, \{ 1 \} , \{ 2 \}, \{ 1,2 \} \}$,


$\mathcal{C} = \{ \{ 1 \} , \{ 2 \}, \{ 1,2 \} \}$,


$\mathcal{C} = \{ \{ 1 \}, \{ 1,2 \} \}$,


$\mathcal{C} = \{ \{ 2 \}, \{ 1,2 \} \}$,


$\mathcal{C} = \{ \{ 1,2 \} \}$, and


$\mathcal{C} = \{ \}$.


So rather than the answer being $2^{2^2} = 16$, there are only 6 valid collections.


Thank you in advance.



How many collections of subsets of {1,2,...,n} are closed under the superset operation?
Such a set is uniquely determined by its minimal members which form an *antichain*. The first few values and some links are [A000372](http://www.research.att.com/~njas/sequences/A000372) in the OEIS


