6
$\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$
13
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.