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

combinatoricsdirected graphsgraph theory

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?

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

Related Question