I am have $n$ vertices and trying to enumerate all possible DAGs $\theta$ over $n$. How many DAGs are there? For example when $n=2$, there are 3 possible DAGs and when $n=3$ I tried the following:

$|E|=0$, $|\theta|=1$

$|E|=1$, $|\theta|=6$

$|E|=2, |\theta|=8$


what is the general formula for counting the number of DAGs with $n$ vertices?


2 Answers 2


This may be too late to be of much help, but I found the following in the documentation for Kevin Murphy's Bayesian Network Toolbox, which can be found here (archive.org).

The number of DAGs as a function of the number of nodes, $G(n)$, is super-exponential in n, and is given by the following recurrence:

$$G(n)=\sum_{k=1}^n (-1)^{k+1}{n \choose k}2^{k(n-k)}G(n-k)$$

The page also lists the number of DAGs for up to 10 nodes.


You'll find answer to these and similar questions also on the Online Encyclopedia for Intersequences, for example entry A003024 gives the number of acyclic digraphs (or DAGs) with $n$ labeled nodes (starting at 0):

1, 1, 3, 25, 543, 29281, 3781503, 1138779265, 783702329343, 1213442454842881, 4175098976430598143, 31603459396418917607425, 521939651343829405020504063, 18676600744432035186664816926721, 1439428141044398334941790719839535103

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .