# How many distinct acyclic paths through a complete graph of size $n$ are there?

Given $$n$$ points on a graph, I want to know how many distinct paths can be formed that:

(1) start at one point and end at a different point
(2) never revisit a point [are acyclic]

Also two paths that traverse the same path but in reverse order are considered the same path.

Is there a closed form formula for calculating this given just $$n$$?

I believe an equivalent way to state this problem is: "how many distinct acyclic paths through a complete graph of size $$n$$ are there?"

I've gotten some leads here but haven't been able to find an answer yet

## 2 Answers

You can just count them based on length. For now, we will ignore that the reverse of a path is the same path.

• There are $$n(n-1)$$ paths of length 1 by picking the origin and terminus.
• There are $$n(n-1)(n-2)$$ paths of length 2.

• ...

• There are $$n!$$ paths of length $$n-1$$.

So, remembering that we have double-counted, the total number of paths in $$K_n$$ is $$\frac12\sum_{k=0}^{n-2}\frac{n!}{k!}=\frac{n!}2\sum_{k=0}^{n-2}\frac1{k!}\approx\frac{en!}{2}$$ where the approximation should be pretty good for large $$n$$.

• Thank you! This explained precisely what I was confused about – Ethan Roland Jan 26 '20 at 2:19

For $$2 \leq k \leq n$$, the number of paths of exactly $$k$$ vertices is given by $$\frac{n(n-1)(n-2)...(n-k+1)}{2}$$. The numerator gives the number of ways to do it without caring about order (there are n ways to pick the first vertex, n-1 for the second, etc.), and then you divide by 2 to cancel both orderings. There are also $$n$$ paths of one vertex and 1 path of zero vertices, if you count those.

This is equal to $$\frac{n!}{2}\sum_{k=0}^{n-2}\frac{1}{k!}$$.