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

ignougroup
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 $(2text{≈}3)*(n-2)!$
Best Answer from StackOverflow

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