How many directed acyclic graphs are there on n labelled nodes?

combinatorics/acyclic.digraphs New

New entry, edited from material collected for the archive and not yet in a released version.

Problem

How many directed acyclic graphs are there on n labelled nodes?  On n
unlabelled nodes?  How many partial orderings are there on n labelled
or unlabelled elements?

[ Editor: problem statement reconstructed from the postings. ]

Show solution

In article <7075@shemp.UCLA.EDU>, verma@CS.UCLA.EDU writes:
>       How many directed acyclic graphs are there over n distinctly
>       labeled nodes?

See R.W. Robinson, Counting labelled acyclic graphs, New directions in
graph theory (Academic Press, 1973) 239-273, and R.P. Stanley, Acyclic
orientations of graphs, Discrete Math. 5 (1973) 171-178.

>       How many directed acyclic graphs are there over n non-distinctly
>       labeled nodes?

See R.W. Robinson, Counting unlabeled acyclic [Editor: "cyclic"
in the original] digraphs, in Combinatorial Math V, Lecture Notes in Math. 622 (1977) 28-43.  For recent
asymptotics on acyclic digraphs, see the papers The Asymptotic Number
of Acyclic Digraphs I (E.A. Bender, L.B. Richmond, R.W. Robinson and
N.C. Wormald; in Combinatorica), and II (E.A. Bender and R.W. Robinson;
in Journal of Combinatorial Theory (B)).  Sorry, don't know vol nos..

>       How many partial orderings are there over n distinctly labeled
>       variables?

I don't know an exact formula.  For asymptotics, see D.J. Kleitman and
B.L. Rothschild, Asymptotic enumeration of partial orders on a finite
set, Trans. Amer. Math. Soc. 205 (1975) 205-220.

>       How many partial orderings are there over n non-distinctly
>       labeled variables?

Again, I only know asymptotics.  See H.J. Promel, Counting unlabeled
structures, Journal of Combinatorial Theory (A) 44 (1987) 83-93.

-- Brendan McKay