edited by
2,146 views
7 votes
7 votes

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

  1. $\displaystyle \sum_{k=1}^{n-1} k!(n-k)!$
  2. $\frac{n!}{2}\bigg[\displaystyle \sum_{k=1}^{n-1} \frac{1}{k(n-k)}\bigg]$
  3. $n!\bigg[\displaystyle \sum_{k=1}^{n-1} \frac{1}{k}\bigg]$
  4. $\frac{n!(n-1)}{2}$
  5. None of the above
edited by

2 Answers

Best answer
16 votes
16 votes

We need to find from $\{1,2,\ldots,n\}$ vertices how many graphs exist which are having exactly two cycles when self loops are allowed.

When $n=1$ there is no such graph with two cycles.

0 graph.

When $n=2$

1 graph exists.

When $n=3$

3 graphs exist.

When $n=4$

11 graphs exist.

For $n=4$

(A) $\sum_{k=1}^{n-1}k!(n-k)! = 16$

(B) $\frac{n!}{2}[\sum_{k=1}^{n-1}\frac{1}{k(n-k)}] = 11$

(C) $n![\sum_{k=1}^{n-1}\frac{1}{k}] = 44$

(D) $\frac{n!(n-1)}{2} = 36$

Option B is answer.

edited by
14 votes
14 votes

Answer : Option B

Let the first cycle contain k vertices and the second cycle contain n-k vertices. Now we can choose k vertices in nCk ways. The k vertices in the first cycle can be arranged in (k-1)! to give different cycles (here, directed graph is mentioned. So clockwise and anticlockwise ordering will be counted as different and hence, no need to divide it by 2). Similarly, the remaining n-k vertices in the second cycle can be arranged in (n-k-1)! ways to give different cycles. Thus, the total number of cycles, will be given as

 

f(k)   = $\binom{n}{k}.(k-1)!.(n-k-1)!$

        = $\tfrac{n!}{(k.(k-1)! . (n-k).(n-k-1)!)} . (k-1)! . (n-k-1)!$

        = $\tfrac{n!}{k(n-k)}$

The value of k can range from 1 to n-1, and summing up all the cases will give us the total number of graphs that will have exactly two cycles. However, here we are distinguishing between first and second cycles. So we will need to divide by 2 because each graph will be counted twice. (Consider two graphs G1 and G2 such that first cycle of G1 is same as second cycle of G2 and vice versa. We have counted these graphs twice but essentially they are the same and so we need to divide the total number by 2). Therefore, the total number of graphs will be:-

$T =\tfrac{1}{2} \sum_{k=1}^{n-1} \tfrac{n!}{k(n-k)} = \tfrac{n!}{2} \sum_{k=1}^{n-1} \tfrac{1}{k(n-k)}$

 

 

edited by
Answer:

Related questions

5 votes
5 votes
1 answer
2
6 votes
6 votes
5 answers
4