expected number of cycles in a "random" bipartite directed graph Consider a "random" bipartite directed graph where (1) on each side, the set of vertices has cardinality n and (2) for each vertex i, we add one (and only one) directed edge i->j at random (drawn uniformly over the n possible directed edges).
Clearly, for all n, and any possible realization of the random graph, there is at least one cycle. 
But what's the expected number of cycles when n tends to infinity? Given k (even), what's the expected number of cycles of size k when n tends to infinity?
I suppose this problem is standard... I would be greatful if one could give me references on this.
Thanks!
 A: There are 
$$ \frac{\prod_{i=0}^{k-1}(n-i)^2}{k} $$
possible directed cycles with $2k$ vertices.  Each such cycle occurs with probability $n^{-2k}$, so the exact expectation of the number of cycles is
$$ \sum_{k=1}^n \frac{\prod_{i=0}^{k-1}(n-i)^2}{kn^{2k}}
 = \sum_{k=1}^n \frac{\prod_{i=0}^{k-1}(1-i/n)^2}{k}. $$
As $n\to\infty$, that sum is asymptotic to the integral
$$ \int_1^\infty \exp(-x^2/n)/x~dx
 = \left[ -\frac12 Ei(1,x^2/n) \right]_1^\infty = \frac12\log n + O(1),
$$
where $Ei$ is the exponential integral function and I'm relying on Maple a bit.
A: You should try
Flajolet, P.; Odlyzko, A. (1990), "Random mapping statistics", Advances in Cryptology – EUROCRYPT '89: Workshop on the Theory and Application of Cryptographic Techniques, Lecture Notes in Computer Science, 434, Springer-Verlag, pp. 329–354.
They don't solve the same problem, exactly — they look at a non-bipartite random graph where each vertex has a single uniformly random outgoing edge, rather than bipartite graph — but it's similar enough that it might be helpful to you. They show that the expected number of cycles (or equivalently components) is $\tfrac{1}{2}\log n$.
