If we allow cycles, then there are three possibilities for an edge between a pair of vertices in a directed graph: no edge, or an arrow in either direction. Since a graph of n vertices has n choose 2 pairs, the total number of DAGs of n vertices has an upper bound of 3^(n choose 2). This is much smaller than n^n.
edit: the last sentence is wrong.
Gwern, thanks for writing more, I will have more to say later.
Since a graph of n vertices has n choose 2 pairs, the total number of DAGs of n vertices has an upper bound of 3^(n choose 2). This is much smaller than n^n.
It is much larger. 3nchoose2 = ((√3^{n-1})^n), and
(√3^{n-1}) is much larger than n.
3^(10 choose 2) is about 10^21.
Since the nodes of these graphs are all distinguishable, there is no need to factor out by graph isomorphism, so 3^(n choose 2) is the exact number.
That’s the number of all directed graphs, some of which certainly have cycles.
So it is. 3^(n choose 2) >> n^n stands though.
A lower bound for the number of DAGs can be found by observing that if we drop the directedness of the edges, there are 2^(n choose 2) undirected graphs on a set of n distinguishable vertices, and each of these corresponds to at least 1 DAG. Therefore there are at least that many DAGs, and 2^(n choose 2) is also much larger than n.
If we allow cycles, then there are three possibilities for an edge between a pair of vertices in a directed graph: no edge, or an arrow in either direction. Since a graph of n vertices has n choose 2 pairs, the total number of DAGs of n vertices has an upper bound of 3^(n choose 2). This is much smaller than n^n.
edit: the last sentence is wrong.
Gwern, thanks for writing more, I will have more to say later.
It is much larger. 3nchoose2 = ((√3 ^{n-1})^n), and (√3 ^{n-1}) is much larger than n.
3^(10 choose 2) is about 10^21.
Since the nodes of these graphs are all distinguishable, there is no need to factor out by graph isomorphism, so 3^(n choose 2) is the exact number.
The precise asymptotic is
That’s the number of all directed graphs, some of which certainly have cycles.
So it is. 3^(n choose 2) >> n^n stands though.
A lower bound for the number of DAGs can be found by observing that if we drop the directedness of the edges, there are 2^(n choose 2) undirected graphs on a set of n distinguishable vertices, and each of these corresponds to at least 1 DAG. Therefore there are at least that many DAGs, and 2^(n choose 2) is also much larger than n.
Yup you are right, re: what is larger.