Say you have n vertices, and you create a directed graph s.t. each vertex has out-degree 1 (this is therefore a functional digraph). Loop edges are allowed and count as cycle of length 1. Now, is there a way to count the number of directed graphs with exactly 1 cycle?
The answer is $$n^{n-1}(\sum_{k=1}^{2}\frac{(n)_k}{n^k} +2\sum_{k=3}^{n}\frac{(n)_k}{n^k})$$
My argument
I thought to consider how you can create cycles from trees. So, say you are given a tree on n vertices. To ensure that we have out-degree 1, we must add an edge onto the root. This, of course, creates a directed cycle – either it is a loop edge, or the edge goes onto some other node (but, because this is a tree, this would create a directed cycle).
So, I thought about using combinatorics here – suppose you make a 2-cycle. Then, there are n choices for the label of the root, and n-1 choices for other vertex's label. Moreover, there are $n\cdot n$ total choices for the labels of the two vertices. Thus, probability of getting a 2-cycle is $\frac{(n)_2}{n^2}$. But for a 3-cycle, you have $2\cdot\frac{(n)_3}{n^3}$ choices – it is times 2 because you can now switch the orientation of the directed cycle to get a distinct digraph.
Lastly, by Cayley's theorem, there are $n^{n-1}$ such trees. As a result, we get the above answer.
Does my argument work? Firstly, I was not sure about the factor of 2 that I introduce in the sum – should I not also be multiplying the denominator by 2 (because the orientation of the edges can be switched)? Moreover, it does not make sense to me entirely why this avoids double-counting.
Best Answer
Here is an answer using EGFs by way of enrichment as done in Analytic Combinatorics by Flajolet and Sedgewick. Recall Cayley's theorem that there are $n^{n-1}$ rooted labeled trees. Introduce
$$ T(z) = \sum_{n\ge 1} n^{n-1} \frac{z^n}{n!}.$$
Note also that for the corresponding combinatorial class $\mathcal{T}$ we have that
$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \mathcal{T} = \mathcal{Z} \times \textsc{SET}(\mathcal{T}).$$
This gives the functional equation
$$T(z) = z \exp T(z).$$
We seek the combinatorial class
$$\textsc{CYC}(\mathcal{T}) = \bigcup_{q\ge 1} \textsc{CYC}_{=q}(\mathcal{T}).$$
This gives for the EGF
$$C(z) = \log\frac{1}{1-T(z)}$$
so that
$$C'(z) = \frac{T'(z)}{1-T(z)}$$
We thus require
$$(n-1)! [z^{n-1}] C'(z)$$
This is
$$(n-1)! \; \underset{z}{\mathrm{res}} \; \frac{1}{z^{n}} \frac{T'(z)}{1-T(z)}.$$
Now put $T(z) = w$ so that $z = w \exp(-w)$ to get
$$(n-1)! \; \underset{w}{\mathrm{res}} \; \frac{\exp(wn)}{w^{n}} \frac{1}{1-w}.$$
This is
$$\bbox[5px,border:2px solid #00A000]{ (n-1)! \sum_{q=0}^{n-1} \frac{n^q}{q!}.}$$
To conclude observe that we find the following sequence
$$1, 3, 17, 142, 1569, 21576, 355081, 6805296, 148869153, \ldots$$
which points to OEIS A001865, where these data are confirmed.