Dynamics of  a random "quadratic" directed graph Let G be a directed graph on N vertices chosen at random, conditional on the requirement that the out-degree of each vertex is 1 and the in-degree of each vertex is either 0 or 2.  The "periodic" points of G are those contained in a cycle.  What do we know about the statistics of G?  For instance, what is the mean number of periodic points, and how do the cycle lengths look?
By comparison, a random directed graph with all out-degrees 1 (which is to say, the graph of a random function from vertices to vertices) has on order of sqrt(N) periodic points on average.
(Motivation:  the graph of a quadratic rational function f acting on P^1(F_q) looks like this, and I'm wondering what the "expected" dynamics are.) 
 A: Let $G$ be a directed graph on $N$ vertices such that the out-degree of each vertex is 1 and the in-degree is either 0 or $n$. Letting $N=nt$, there are $t$ vertices with in-degree $n$ and $(n-1)t$ vertices with in-degree 0. Assuming the vertices are labeled, the number of such graphs is
$$
\binom{nt}{t}\frac{(nt)!}{(n!)^t}.
$$
For $1\leq m\leq t$, the number of such graphs with a fixed $m$-cycle is
$$
\binom{nt-m}{t-m}\frac{(nt-m)!}{((n-1)!)^m(n!)^{t-m}},
$$
so the number of $m$-periodic points amongst all such graphs is
$$
m\cdot\binom{nt-m}{t-m}\frac{(nt-m)!}{((n-1)!)^m(n!)^{t-m}}\cdot\frac{(nt)!}{m(nt-m)!}=\binom{nt-m}{t-m}\frac{(nt)!}{((n-1)!)^m(n!)^{t-m}}.
$$
Summing over $1\leq m\leq t$, the average we want is
$$
\binom{nt}{t}^{-1}\sum_{m=1}^{t}{n^m\binom{nt-m}{t-m}}=-1+\binom{nt}{t}^{-1}\sum_{m=0}^{t}{n^m\binom{nt-m}{t-m}}.
$$
When $n=1$, the average is $t$ (since all points would be periodic). When $n=2$, as in the question, the sum is 
$$
-1+\frac{4^t}{\binom{nt}{t}}\sim-1+\sqrt{\frac{\pi}{2}}\sqrt{N},
$$
so the number of periodic points does indeed look random. When $n>2$, I haven't found the identity I need yet.
A: To calculate expected numbers of cycle of each length, you should be able to just wade in and use Stirling's approximation to deal with the results.
Let's write $N=2t$. Then there are $t$ vertices with indegree 0 and $t$ with indegree 2. The number of such graphs is $(2t)!/2^t$.
If $a_1,\ldots,a_m$ are vertices with indegree 2, then the number of ways that they can be a cycle (in that order) is
$$\binom{2t-m}{m}\frac{(2t-2m)!}{2^{t-m}},$$
since we first choose other inputs for these vertices, and then deal with what's left.
Then the expected number of $m$-cycles is obtained by multiplying that by $t!/(t-m)!$ and dividing by the number of such graphs. So you can get an exact formula, and then deploy Stirling on it.
