# Finding number of two cycle multi-graphs [closed]

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?

## closed as off-topic by user21820, Saad, RRL, Alexander Gruber♦Mar 24 at 2:54

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – user21820, Saad, RRL, Alexander Gruber
If this question can be reworded to fit the rules in the help center, please edit the question.

• What are your thoughts on the problem? What approaches have you tried? – Santana Afton Mar 23 at 13:04

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)+...$$.