# How many directed acyclic graphs (DAG) s are possible using N vertices?

If all the number of all the possible DAGs are K, then K can consist of

• disconnected vertices (not all connected vertices)
• from the directionality of a particular edge is counted as a new graph

My attempt to analyze: Example for 2 nodes X,Y ;

1. G1 : {X,Y} ( all disconnected)
2. G2 : {X->Y}
3. G3 : {X<-Y} ( directionality changes)

But for 3 nodes X, Y, Z; there are a large number of possible graphs;

1. set 1: with 1 edge
2. set 2: with 2 edges
3. set 3: with 3 edges
4. set 4: with 0 edges

Likewise, the possible space is growing.

I tried, this resource but when I try to cont it for 2 edges it should be (2^(2^2)), but it violates my above analysis. Maybe this solution is not applicable to my situation.

May I know any clue on how to count the number of all the possible DAGs that can be generated using N vertices incorporating the above analysis?

$$a_n=\sum_{k=1}^n(-1)^{k+1}\binom{n}k2^{k(n-k)}a_{n-k}$$
with $$a_0=1$$, but no closed form, so it seems likely that no closed form is known.
• @SachzEMSPE: If I’m not mistaken, it can be derived from Theorem $1$ of the paper by Rodionov noted in the OEIS entry. – Brian M. Scott Oct 18 '20 at 23:33