How many different graphs of order $n$ are there?

Question

I'm interested in all four combinations: directed and undirected, cyclic and acyclic.

I'm having trouble calculating how big the complexity gets as you add more nodes to a graph. Clearly, the number of possible graphs goes up with adding directability, and wildly (adding Ω(2ⁿ) complexity, roughly).

My best guess on a DAG is close to Ω(n!).

This question concerns itself with knowledge representation. How many neural networks are there with n neurons? Given that different knowledge must be encoded differently, it gives some sort of data about how knowledge can scale in the brain.

[Edit: "multigraphs", obviously, aren't part of the question, disconnected graphs should count as their lower order counterparts, and v1 is separate from v2 such that a set V containing both has 3 DAGs.]

[Edit2: Looks like for DCGs, it is about 2³ⁿ. For DAGs, it's about 2²ⁿ.]

[Note: I tagged this under "descriptive complexity" because it's not really a simulation. Let me know if this is wrong.]

Answer 1

In general these counts do not have nice closed formulas, but some satisfy nice recurrence relations.

Graphs

• Graphs on $n$ nodes is OEIS A000088: $$1, 1, 2, 4, 11, 34, 156, 1044, 12346, 274668, \ldots .$$ Flajolet & Sedgwick's Analytic Combinatorics, $\S~$II.5 gives that this sequence is asymptotic to $2^{\frac{1}{2} n (n - 1)}/n!$. (They cite Harary & Palmer's text Graphical Enumeration for this fact, but I haven't checked it myself. Probably that reference gives some of the below data, too.)
• Acyclic graphs on $n$ nodes (forests) is A005195: $$1, 1, 2, 3, 6, 10, 20, 37, 76, 153, \ldots .$$ This is asymptotic to $c n^{-5/2} d^n$ for some $c > 0$ and $d > 1$.
• Cyclic graphs on $n$ nodes is A286743: $$0, 0, 1, 5, 24, 136, 1007, 12270, 274515, 12004839, \ldots .$$ By definition this is just [A000088] - [A005195]. The latter has much smaller growth than the former, so this also asymptotic to $2^{\frac{1}{2} n (n - 1)}/n!$.

Directed graphs

• Directed graphs on $n$ nodes is OEIS A000273: $$1, 1, 3, 25, 543, 29281, 3781503, 1138779265, 783702329343, 1213442454842881, \ldots .$$ This is asymptotic to $2^{n (n - 1)}/n!$
• Directed acyclic graphs on $n$ nodes is OEIS A003087: $$1, 1, 2, 6, 31, 302, 5984, 243668, 20286025, 3424938010, \ldots .$$ OEIS doesn't give asymptotics for this sequence, but we can deduce from asymptotics for the case of labeled directed acyclic graphs that this sequence is asymptotic to some function in between $A p^{-n} 2^{\frac{1}{2} n (n - 1)}$ and $A p^{-n} 2^{\frac{1}{2} n (n - 1)} n!$ for some $A > 0$ and $p > 1$. In any case before this is much slower growth than the count for directed graphs, so graphs on $n$ nodes that have at least one cycle is also asymptotic to $2^{n (n - 1)} / n!$.