# Number of subsets on a set with partial order

Given a set $S$ with strict partial order $<$. Let $A\subseteq S$ be a downward-closed subset of $S$ (in other words, if $a<b$ and $b\in A$, then $a\in A$). How many subsets of $S$ are downward-closed?

Are there algorithms that can solve the problem in time polynomial in $|S|$?

• Is there any particular reason for using $<$ instead of $\leq$? Nov 6 '11 at 4:23
• strict order make sure the graph is for the order is a DAG. Nov 6 '11 at 4:27

An additional comment: in case your partially ordered set is the power set of a given set (e.g., [n]) ordered by the inclusion, more is known when n is small. Specifically see the Dedekind numbers article and the Sloane integer sequence. The asymptotic behavior has been studied also. Hansel in 1966 proved that the number of antichains of subsets of an n-set is upper-bounded by $3^{{n \choose \lfloor n/2\rfloor}}$. Later, Kleitman and Markowsky improved this bound. For further results see the references in this Wikipedia article. Finally, another reference (in addition to the Provan-Ball paper which appears in one of the links above) of interest to you probably is "On the relative complexity of approximate counting problems", by Dyer, Goldberg, Greenhill and Jerrum.