7
$\begingroup$

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$

$|E|=3,|\theta|=3$

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

$\endgroup$

2 Answers 2

17
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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
$\endgroup$

You must log in to answer this question.

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