<p>See three closely related questions <a href="https://cstheory.stackexchange.com/questions/7679/does-faster-exact-algorithm-for-counting-independent-sets-in-comparability-graph">Does faster exact algorithm for counting independent sets in comparability graphs than general graph exisits?</a> and <a href="https://cstheory.stackexchange.com/questions/7637/is-counting-maximal-cliques-in-an-incomparability-graph-p-complete">Is counting maximal cliques in an incomparability graph #P-complete?</a> and <a href="https://mathoverflow.net/questions/49515/on-the-number-of-antichains-of-a-poset">https://mathoverflow.net/questions/49515/on-the-number-of-antichains-of-a-poset</a></p>

<p>They are all on antichains rather than downward-closed sets but downward-closed sets correspond one-for-one with the antichains of their maximal elements.</p>

<p>I believe both of the cstheory questions have answers with references that also answer your question: no, the problem is #P-complete.</p>

CC BY-SA 3.0
2011-11-06T05:02:16.110Z
2011-11-06T05:02:16.110Z
2017-04-13T12:57:54.777Z
David Eppstein
<p>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 <a href="http://en.wikipedia.org/wiki/Dedekind_number">Dedekind numbers</a> article and the <a href="http://oeis.org/A000372">Sloane integer sequence</a>. 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 <a href="http://en.wikipedia.org/wiki/Dedekind_number">Wikipedia article</a>. Finally, another reference (in addition to the Provan-Ball paper which appears in one of the links above) of interest to you probably is <a href="http://www.google.com/url?sa=t&amp;rct=j&amp;q=on%20the%20relative%20complexity%20of%20approximate%20counting%20problems&amp;source=web&amp;cd=1&amp;ved=0CCUQFjAA&amp;url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.88.5821%26rep%3Drep1%26type%3Dpdf&amp;ei=OB22TqywLYXq0gGEwdzSBw&amp;usg=AFQjCNF1OpHwdY0jm_jQtsnwAU7DzfVsFQ&amp;sig2=IJaqI2GexuH0xijrV8ROcQ">"On the relative complexity of approximate counting problems"</a>, by Dyer, Goldberg, Greenhill and Jerrum. </p>

CC BY-SA 3.0
2011-11-06T05:55:00.927Z
2011-11-06T05:55:00.927Z
Babis Tsourakakis 
<p>Given a set $S$ with strict partial order $&lt;$. Let $A\subseteq S$ be a downward-closed subset of $S$ (in other words, if $a&lt;b$ and $b\in A$, then $a\in A$). How many subsets of $S$ are downward-closed?</p>

<p>Are there algorithms that can solve the problem in time polynomial in $|S|$?</p>

CC BY-SA 3.0
2011-11-06T04:23:46.327Z
Is there any particular reason for using $<$ instead of $\leq$?
Timothy Sun
CC BY-SA 3.0
2011-11-06T04:27:57.853Z
strict order make sure the graph is for the order is a DAG.
Chao Xu
<ds.algorithms><counting-complexity><partial-order>
Number of subsets on a set with partial order
Chao Xu
# Number of subsets on a set with partial order

(Asked by: username_0 on 2011-11-06)

Given a set $S$ with strict partial order $<$. Let $A\subseteq S$ be a downward-closed subset of $S$ (in other words, if $a

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

**Tags:** ds.algorithms, counting-complexity, partial-order

> **Comments:**
> **username_1**: Is there any particular reason for using $<$ instead of $\leq$?  
> **username_0**: strict order make sure the graph is for the order is a DAG.  

---

## 2 answers

### Answer by username_2 on 2011-11-06. Score: 8 | Accepted answer

See three closely related questions [Does faster exact algorithm for counting independent sets in comparability graphs than general graph exisits?](https://cstheory.stackexchange.com/questions/7679/does-faster-exact-algorithm-for-counting-independent-sets-in-comparability-graph) and [Is counting maximal cliques in an incomparability graph #P-complete?](https://cstheory.stackexchange.com/questions/7637/is-counting-maximal-cliques-in-an-incomparability-graph-p-complete) and <https://mathoverflow.net/questions/49515/on-the-number-of-antichains-of-a-poset>

They are all on antichains rather than downward-closed sets but downward-closed sets correspond one-for-one with the antichains of their maximal elements.

I believe both of the cstheory questions have answers with references that also answer your question: no, the problem is #P-complete.


---

### Answer by username_3 on 2011-11-06. Score: 6

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](http://en.wikipedia.org/wiki/Dedekind_number) article and the [Sloane integer sequence](http://oeis.org/A000372). 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](http://en.wikipedia.org/wiki/Dedekind_number). 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"](http://www.google.com/url?sa=t&rct=j&q=on%20the%20relative%20complexity%20of%20approximate%20counting%20problems&source=web&cd=1&ved=0CCUQFjAA&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.88.5821%26rep%3Drep1%26type%3Dpdf&ei=OB22TqywLYXq0gGEwdzSBw&usg=AFQjCNF1OpHwdY0jm_jQtsnwAU7DzfVsFQ&sig2=IJaqI2GexuH0xijrV8ROcQ), by Dyer, Goldberg, Greenhill and Jerrum.


---

