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 1


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


with $a_0=1$, but no closed form, so it seems likely that no closed form is known.

  • $\begingroup$ 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. $\endgroup$
    – Sachz
    Oct 18, 2020 at 23:25
  • 1
    $\begingroup$ @SachzEMSPE: If I’m not mistaken, it can be derived from Theorem $1$ of the paper by Rodionov noted in the OEIS entry. $\endgroup$ Oct 18, 2020 at 23:33
  • 1
    $\begingroup$ Thank you for the resource! It is accessible. Let me give it a try. $\endgroup$
    – Sachz
    Oct 18, 2020 at 23:44
  • $\begingroup$ @SachzEMSPE: You’re welcome! $\endgroup$ Oct 18, 2020 at 23:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.