0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you! This explained precisely what I was confused about $\endgroup$ – Ethan Roland Jan 26 at 2:19
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.