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

Question

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

Answer 1

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

Answer 2

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