[Solved]: Count of all simple paths between two vertices in a Complete graph

Problem Detail: 

A path is simple if it repeats no vertices. How many simple paths between two vertices in Complete graph?

One way is listing the simple paths is to use depth-first search. but i think it should be simple to find the number of all path between 2 nodes in Complete graph.

Here is same problem but mine is for Complete graph: Algorithm that finds the number of simple paths from $s$ to $t$ in $G$

Asked By : Ali

Answered By : Ali

$c(1)=0,$

$c(n)=(n-2)*c(n-1)+1$

suppose we have c(n-1) path in (n-1)-Complete Graph. when we add one more vertices, we add $(n-2)*c(n-1)$ new path and one for directed path.

the result is same as real:

1. 0
2. 1
3. 2
4. 5
5. 16

6. 65

   ===============================EDITED

   $c(n)=\sum_{i=0}^{n-2} \frac{(n-2)!}{i!}=(n-2)!*\sum_{i=0}^{n-2}\frac{1}{i!}$

   .

   This shows that's about $(2\text{≈}3)*(n-2)!$

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/29558