Given number of vertices $k$, how many DAGs over $k$ are there? I know from here that it can be computed in a recursive manner. I am wondering whether there are other simple formulas.

  • $\begingroup$ This is such beautiful theorem that is worth looking at. $\endgroup$ – LASV Dec 4 '13 at 0:58
  • $\begingroup$ @Luis this is similar to the Wiki one and it seems the only known formula to compute it. My next question is this number always greater than $2^k$? $\endgroup$ – seteropere Dec 4 '13 at 1:54
  • 1
    $\begingroup$ To be completely honest, I do not know that much about graph theory. This is just a result I remember from my combinatorics class. $\endgroup$ – LASV Dec 4 '13 at 1:57
  • 1
    $\begingroup$ Is $a\to b$ different from $b\to a$? If so, then there are at least $k!$ of them, just counting the different orderings of $k$ objects, and that's much bigger than $2^k$. $\endgroup$ – Gerry Myerson Dec 4 '13 at 2:19
  • 2
    $\begingroup$ The source is half-a-minute's thought. $2^k$ is a product of $k$ numbers, each of which is a 2. $k!$ is also the product of $k$ numbers, almost all of which are bigger than 2. Can you take it from there? $\endgroup$ – Gerry Myerson Dec 4 '13 at 4:38

Your Answer

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

Browse other questions tagged or ask your own question.