# 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?

## 1 Answer

This is OEIS A003024. The entry has number of references, an asymptotic approximation, and the recurrence

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

• I see, Thank you for helping! I I was wondering how to derive this, hence I tried to find the resource R. W. Robinson, Counting labeled acyclic digraphs., but I could not find an accessible resource. I would appreciate it if could suggest any accessible resource on this? Meanwhile, I found this paper which cites the same resource, but it mentioned the recurrence in a different way. So, I'm really interested in the derivation of this equation. – Sachz Oct 18 '20 at 23:25
• @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
• Thank you for the resource! It is accessible. Let me give it a try. – Sachz Oct 18 '20 at 23:44
• @SachzEMSPE: You’re welcome! – Brian M. Scott Oct 18 '20 at 23:47