I'm going to assume that you're counting *maximal* antichains because the word "maximal" occurs in the title, even though it doesn't appear in the main text of your question.

You will probably find more literature if you phrase your problem as counting maximal cliques in an incomparability graph. For a general graph, Valiant showed that counting the number of maximal cliques is #P-complete (*SIAM J. Computing* **8** (1979), 410–421). I am not sure whether the problem remains #P-complete when restricted to incomparability graphs. Incomparability graphs are perfect, so at least it's possible to determine the size of the largest clique in polynomial time, but that doesn't immediately imply anything about the complexity of the counting problem. You could try asking your question on cstheory.stackexchange.com.

There are algorithms that enumerate maximal cliques in time polynomial in the number of maximal cliques, so if the total number of maximal cliques is polynomial then you can count them in polynomial time. See for example the paper by Rosgen and Stewart. In general, though, incomparability graphs could have exponentially many maximal cliques.

**EDIT:** I still don't know whether your problem is #P-complete, but I'm beginning to suspect that it is. If so, perhaps the techniques in Salil Vadhan's paper "The complexity of counting in sparse, regular, and planar graphs" (*SIAM J. Comput.* **31** (2001), 398–427) will be useful for proving it.

what? – Qiaochu Yuan Aug 3 '11 at 15:52