# How many possible DAGs are there with $n$ vertices

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?

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)$$