# 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

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!}$$.