Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 asymmetric, 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.

share|improve this question

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.