How to calculate the number of simple cycles in a complete, directed graph.

602 Views Asked by At

In his article "Finding all the elementary circuits of a directed graph", Donals B. Johnson provides the following equations and states that it calculates the number of elementary circuits in a complete directed graph with n vertices. $$ \sum_{i=1}^{n-1}\binom{n}{n-i+1}(n-i)! $$

And I was wondering how to rewrite the middle-parentheses and calculate this as I am not sure whether this is the notation for combinations, permutations or something else.

1

There are 1 best solutions below

3
On

It would make more sense to me to write it as $$ \sum_{j=2}^{n} \binom{n}{j}(j-1)! $$ or perhaps $$ \sum_{j=2}^{n} \binom{n}{j} \frac{j!}{j}, $$ that is, the number of ways to pick $j$ of the $n$ vertices, and choose a cyclic order of those $j$ vertices.

I started at 2, assuming that a single vertex is not a cycle. With an undirected graph, we'd probably say two vertices can't be a cycle, and start with $j = 3$.

But starting from $j = 2$ is equivalent to your formula, with the substitution $i = n - j + 1$.