Finding number of two cycle multi-graphs

Question

Consider directed graphs on n labelled vertices {1,2,...n}, where each vertex has exactly one edge coming in and exactly one edge going out. We allow self-loops. How many such graphs have exactly two cycles?

Answer 1

Let us use $(m,n)$ to denote the length of the two cycles found in the graph. So consider a graph with $n$ vertices.

For $n=2$ we have $(1,1)$ as a possible cycles length.

For $n=3$, we have $(1,1) (1,2)$

For $n=4$, we have $(1,1) (1,2) (1,3) (2,2)$

For $n=5$, we have $(1,1) (1,2) (1,3) (1,4) (2,2) (2,3)$

For $n=6$, we have $(1,1) (1,2) (1,3) (1,4) (1,5) (2,2) (2,3) (2,4) (3,3)$

From the above pattern, we can deduce a formula. So the formula seems to be defined as follow: for a graph on $n$ vertices, it has $(n-1)+(n-3)+(n-5)+...$ ways to have only $2$ cycles. And in the above sum, a term that gives a negative value should be omitted. Let $f_m(n)$ be the characteristic function that is 0 everywhere except for $n\geq m$. then the solution is $(n-1)f_2(n)+(n-3)f_4(n)+(n-5)f_6(n)+...$.