So we have that the expected number of Hamiltonian cycles in the random graph $G(n,p)$ is given by:
$\mu_{n}(p)=\frac{1}{2}(n-1)!p^{n}$ for $n \geq 3$.
We now want to find lim$_{n\to \infty}\mu_{n}(\frac{c}{n})$, where $c$ is a constant.
Ok, we know that $0 \leq p \leq 1$ $\implies$ $0 \leq \frac{c}{n} \leq 1 \implies c \geq 0$ and $n \geq c$. I'm not sure how one should think about the last constraint, i.e. that $n \geq c$. So when we think about evaluating lim$_{n\to \infty}\mu_{n}(\frac{c}{n})$ do we just fix some $c \geq 0$? But then, for instance if take $c = 111$ and let $n$ go to infinity, for $n<111$ we're considering events with probability $>1$ which doesn't make sense. Or does it? Or should we restrict $c$, s.t. $0\leq c \leq 3$, so the constraints above are always satisfied?
How would we then go about finding lim$_{n\to \infty}\mu_{n}(\frac{c}{n})$?
Best Answer
We can use Stirling's approximation, in the form $$ n! \sim \sqrt{2 \pi n} \left(\frac ne\right)^n. $$ Here, we have $$ \mu_n(\tfrac cn) = \frac{n! \cdot (\frac cn)^n}{2n} \sim \sqrt{\frac{\pi}{2n}} \left(\frac ne\right)^n \left(\frac cn\right)^n = \sqrt{\frac{\pi}{2n}} \left(\frac ce\right)^n. $$ Therefore,
In a finer parametrization $$ p(n) = \frac{en + \frac12\ln n + f(n)}{n^2}, $$ the same approximation shows that $$ \mu_n(p(n)) \sim \sqrt{\frac\pi 2} e^{f(n)} $$ and the behavior of $f(n)$ determines the behavior of $\mu_n(p(n))$.