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?
Best Answer
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.