# What is average number of cycles in an undirected ordered graph of size n?

What is average number of cycles in an undirected ordered graph of size $n$? I've tried finding out sum of number of cycles in all sorts of a graph of size n but I couldn't find that out.

-
What specifically have you tried resp where have you looked? – Raphael Apr 1 '14 at 11:45

Hint: Suppose that there are $Z_m$ cycles of length $m$, and that $p_m$ is the probability that a specific cycle of length $m$ is in the graph. Then the expected number of cycles is $$\sum_{m=3}^n Z_m p_m$$ due to linearity of expectation.
Here is the entire calculation. In the $G(n,p)$ model, in which each edge is present with probability $p$ independently, clearly $p_m = p^m$. The number of ordered $m$-tuples of points is $n!/(n-m)!$. Each cycle of length $m$ is described by $2m$ such tuples: choose a starting point and an orientation. Therefore the total number of cycles of length $m$ is $n!/2m(n-m)!$, and the expected number of cycles is $$E = \sum_{m=3}^n \frac{n!}{2m(n-m)!} p^m.$$
In order to estimate this number, let's find the largest term. The ratio of two successive terms is roughly $$\frac{p^{m+1}}{(n-m-1)!} \frac{(n-m)!}{p^m} = (n-m)p.$$ When $p$ is constant, we see that the most important term corresponds to $m = n$, namely $n! p^n/(2n)$, and we deduce that for large enough $n$, the expected number of cycles satisfies $$2(n-1)! p^n \leq E \leq 2n! p^n.$$