# number of directed acyclic graphs

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.

• This is such beautiful theorem that is worth looking at. – LASV Dec 4 '13 at 0:58
• @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$? – seteropere Dec 4 '13 at 1:54
• To be completely honest, I do not know that much about graph theory. This is just a result I remember from my combinatorics class. – LASV Dec 4 '13 at 1:57
• 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$. – Gerry Myerson Dec 4 '13 at 2:19
• 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? – Gerry Myerson Dec 4 '13 at 4:38