= 27d567bc2d48d9f40e9ccc20ea370b15)
RichardKennaway comments on Confound it! Correlation is (usually) not causation! But why not? - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (34)
It is much larger.
= ^{n-1})^n)
, and ^{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%202%5E{\binom{n}{2}}%20\omega%5E{-n})
, as shown on page 4 of this article. Here lambda and omega are constants between 1 and 2.
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.