# Number of posets (equivalently: transitive DAGs) with labeled elements

It's hard to count the number of posets with a given number of elements; Sloane's A001035 has it only up to 18. Are asymptotic results known?

My actual interest is in transitive relations, Sloane's A006905, but it's not hard to convert between these. I would accept an answer giving either.

[1] Götz Pfeiffer, Counting Transitive Relations, Journal of Integer Sequences 7 (2004).

[2] R. P. Stanley, Enumerative Combinatorics, 1986.

-

If you look at:

http://en.wikipedia.org/wiki/Directed_acyclic_graph#Enumeration

And then look at the cited paper by our own contributor B. McKay et al, section 3 (the paper is freely available) they discuss asymptotics, and give references to papers by E. Bender et al (references 1, 2 in the paper). The paper (ref 4) by Gessel counts by number of sources and sinks, which is surely within $\epsilon$ of what you seek.

-
That does seem to answer the question I asked. Unfortunately... what I actually wanted was A001035, not A003024. Any ideas? – Charles Sep 5 '11 at 18:21

The asymptotics for acyclic graphs is not the same as for those that are transitive. The asymptotics for posets is given in D. J. Kleitman and B. L. Rothschild, Trans. Amer. Math. Soc. 205 (1975), 205-220.

-
You're right, I misstated the problem. My ultimate interest is the number of transitive relations on a relation with labeled elements, Pfeiffer's T(n). – Charles Sep 5 '11 at 18:22
If $f(n)$ is the number of $n$-element posets, or labelled posets, or transitive relations, or labelled transitive relations, etc., then $f(n)= 2^{\frac{n^2}{4} + o(n^2)}$. If you want an asymptotic rather than logarithmically asymptotic formula, then the situation is more delicate and depends on the precise objects being enumerated. – Richard Stanley Sep 5 '11 at 21:11