If I have a directed graph with $n$ vertices, and the mean number of out-edges per vertex is $x$, what is the expected number of simple circuits that will be found in the graph?
What happens to the result if we introduce the constraint that each edge can belong to only one circuit?
Thanks in advance.
There are, on average, $\binom{n-1}{x}$ ways to choose an outgoing neighborhood of $v_{1}$. The vertex $v_{2}$ will be $\binom{n-2}{x-1}$ of these neighborhoods. So simply divide out: $$P( (v_{1}, v_{2}) \in E(G) ) = \dfrac{ \binom{n-2}{x-1} } { \binom{n-1}{x} }$$
Now for a two-cycle, we want an outgoing arc from $v_{2}$ to $v_{1}$. The probability is the same as we found above, so we multiply. There are $\binom{n}{2} p(C_{2})^{2}$ such cycles we would expect.
For three cycles, we start with by going from $v_{1} \to v_{2}$, with probability $ \dfrac{ \binom{n-2}{x-1} } { \binom{n-1}{x} }$. We then pick $v_{3}$, and it has the same probability of being in $v_{2}$'s neighborhood.
So now we want the probability of $v_{3}$ having $v_{1}$ in its neighborhood, which is again the same probability as above. So $E(C_{3}) = \binom{n}{3} (\dfrac{ \binom{n-2}{x-1} } { \binom{n-1}{x} })^{3}$.
Do you see the logic as to how I'm counting? Do you see the pattern to add up?