Asymptotic number of unlabeled graphs

Question

A rather tight lower bound $c(n)$ of the number of unlabeled digraphs of order $n$ (loops allowed) seems to be

$$c(n) = 2^{n^2}/n!$$

because there are $2^{n^2}$ labeled graphs, almost all of them are rigid, thus division by $n!$ is almost always "correct", but yields a slightly too small result, because it is sometimes not correct. How can this error be estimated, of which order is it? But most of all I'd like to know:

Is the growth rate of $c(n)$ super- or supra-exponential?

I know Stirling's formula, but I didn't manage to simplify the resulting expression.

Answer 1

If you apply Stirling's formula,

$c(n)\approx \frac{2^{n^2}e^{-n}}{n^n}$.

$\log c(n)\approx n^2 \log 2 - n \log n + n$

As the log increases faster than $n$, the growth is faster than any exponential.

Answer 2

See the OEIS, sequence A000088 for an asymptotic formula for the error. In particular, if $G(n)$ is the number of unlabeled graphs on n nodes, then

$$ {G(n) \over c(n)} = 1 + {n^2 - n \over 2^{n-1}} + O(n^2 2^{-2n}) $$

as $n \to \infty$. I suspect there is a simple combinatorial explanation for that first term but I don't know what it is; the source is Harary and Palmer, Graphical Enumeration, which may explain that.