I've been struggling with a proof for several days now and I just can't quite see how it works. I am trying to prove the limit of the number of graphs with n vertices up to isomorphism is:
$$ \frac{2^{n \choose 2}}{n!}$$
I have been using this Harary and Palmer formula for enumerating graphs of order p by number of lines:
Above, to be clear, $j_k$ represents the number of k-cycles in a given permutation α, $(r, t)$ represents the greatest common divisor of r and t, and $[r, t]$ represents the least common multiple of r and t. I can see where the $n \choose 2$ comes from but I am struggling to understand the rest of the formula and how to find limits of the other products.
Any help would be really appreciated as I have been struggling with it for a long time now! Thank you.
This is a classic result, first due to Polya, but probably many others rediscovered/refined it too. See any book on random graphs (e.g., Bollobas) for this statement: $G_{n,1/2}$, the random graph on vertex set $\{1,\dots,n\}$ where each edge is included independently with probability $1/2$, has trivial automorphism group with very high probability. This proves what you want because the number of labeled graphs on $n$ vertices is $2^{\binom{n}{2}}$, and almost all of them correspond to $n!$ unlabelled graphs.
I sketch a proof from: http://www.fields.utoronto.ca/programs/scientific/11-12/constraint/summerschool/nesetril.pdf. Essentially, the idea is to count the number of labeled graphs with nontrivial automorphism group. A nontrivial automorphism must move many vertices by degree/codegree assumptions, giving an upper bound on the number of orbits of edges, which in turn limits the number of choices for the original graph.