<s>[INST] asymptotics of the expected number of edges of a random acyclic digraph with indegree and outdegree at most one A recent discussion, which may be found here, examined the problem of counting the number of acyclic digraphs on $n$ labelled nodes and having $k$ edges and indegree and outdegree at most one. It was established that the bivariate mixed generating function of this class $\mathcal{G}$ of graphs on $n$ nodes and with $k$ edges is
$$ G(z, u) = \exp \left(\frac{z}{1-uz} \right).$$
This immediately implies that the expected number of edges of a random graph from $\mathcal{G}$ is
$$\epsilon_n = [z^n]\left. \frac{d}{du} G(z,u) \right|_{u=1}.$$
Evaluating this quantity we obtain
$$ \left. \exp \left(\frac{z}{1-uz} \right) z (-1)\frac{1}{(1-uz)^2} (-z)\right|_{u=1}
= \left. \exp \left(\frac{z}{1-uz} \right) \frac{z^2}{(1-uz)^2} \right|_{u=1}
= \exp \left(\frac{z}{1-z}\right) \left(\frac{z}{1-z}\right)^2$$
Continuing with this calculation we find
$$ \epsilon_n = [z^n] \sum_{m\ge 0} \frac{1}{m!}  \left(\frac{z}{1-z}\right)^{m+2} =
\sum_{m=0}^{n-2} \frac{1}{m!} [z^n]  \left(\frac{z}{1-z}\right)^{m+2} =
\sum_{m=0}^{n-2} \frac{1}{m!} [z^{n-m-2}] \left(\frac{1}{1-z}\right)^{m+2} =
\sum_{m=0}^{n-2} \frac{1}{m!} \binom{n-m-2+m+1}{m+1} =
\sum_{m=0}^{n-2} \frac{1}{m!} \binom{n-1}{m+1}.$$
This closed form is actually quite nice, but it does not answer the question that is the most obvious one for this problem, namely Is there an asymptotic expansion of $\epsilon_n$ and if yes, what is the first term?
 [/INST] We can expand this calculation to the variance in addition to the expected value. To do so we compute $$E[X(X-1)] = \frac{ [z^n] \left. \left(\frac{d}{du}\right)^2 G(z, u) \right|_{u=1}}{[z^n] G(z, 1)}$$ where $X$ is the RV representing the number of edges.
Now $$\left. \left(\frac{d}{du}\right)^2 G(z, u) \right|_{u=1} =
\left.\left( \frac{d}{du}\right)\exp\left(\frac{z}{1-uz}\right) \left(\frac{z}{1-uz}\right)^2 \right|_{u=1} =
\left.\exp\left(\frac{z}{1-uz}\right) \left(\frac{z}{1-uz}\right)^4 +
2 \exp\left(\frac{z}{1-uz}\right) \left(\frac{z}{1-uz}\right)^3 \right|_{u=1} =
\exp\left(\frac{z}{1-z}\right) \left(\frac{z}{1-z}\right)^4 +
2 \exp\left(\frac{z}{1-z}\right) \left(\frac{z}{1-z}\right)^3$$
Now expand the two terms in turn.
Left term,
$$[z^n] \exp\left(\frac{z}{1-z}\right) \left(\frac{z}{1-z}\right)^4  =
[z^n] \sum_{m\ge 0} \frac{1}{m!} \left( \frac{z}{1-z}\right)^{m+4} =
[z^n] \sum_{m=0}^{n-4} \frac{1}{m!} \left( \frac{z}{1-z}\right)^{m+4} $$ or $$
\sum_{m=0}^{n-4} \frac{1}{m!} [z^{n-m-4}] \left( \frac{1}{1-z}\right)^{m+4} =
\sum_{m=0}^{n-4} \frac{1}{m!} \binom{n-m-4+m+3}{m+3} = 
\sum_{m=0}^{n-4} \frac{1}{m!} \binom{n-1}{m+3}.$$
Right term,
$$2 [z^n] \exp\left(\frac{z}{1-z}\right) \left(\frac{z}{1-z}\right)^3  =
2 [z^n] \sum_{m\ge 0} \frac{1}{m!} \left( \frac{z}{1-z}\right)^{m+3} =
2 [z^n] \sum_{m=0}^{n-3} \frac{1}{m!} \left( \frac{z}{1-z}\right)^{m+3} $$ or $$
2 \sum_{m=0}^{n-3} \frac{1}{m!} [z^{n-m-3}] \left( \frac{1}{1-z}\right)^{m+3} =
2 \sum_{m=0}^{n-3} \frac{1}{m!} \binom{n-m-3+m+2}{m+2} = 
2 \sum_{m=0}^{n-3} \frac{1}{m!} \binom{n-1}{m+2}.$$
It follows that $$E[X(X-1)] = 
\frac{\sum_{m=0}^{n-4} \frac{1}{m!} \binom{n-1}{m+3} + 2 \sum_{m=0}^{n-3} \frac{1}{m!} \binom{n-1}{m+2}}{\sum_{m=1}^n \frac{1}{m!} \binom{n-1}{m-1}}.$$
The question now becomes, what is the asymptotic expansion of this quotient of sums? That would put the variance within reach, given that $E[X^2] = E[X(X-1)] + E[X].$
</s>