In a complete graph total number of paths between two nodes is equal to:
$\lfloor(P-2)!e\rfloor$
This formula doesn't make sense for me at all, specially I don't know how ${e}$ plays a role in this formula. could anyone prove that simply with enough explanation?
Best Answer
I assume $P$ is the number of nodes.
The actual number of paths between the two nodes which have $k$ extra vertices is $\frac{(P-2)!}{(P-2-k)!}$, for $0\leq k\leq P-2$. This is because you can choose $k$ other nodes out of the remaining $P-2$ in $\frac{(P-2)!}{(P-2-k)!k!}$ ways, and then you can put those $k$ nodes in any order in the path.
So the total number of paths is given by adding together these values for all possible $k$, i.e. $$\sum_{k=0}^{P-2}\frac{(P-2)!}{(P-2-k)!}=(P-2)!\sum_{j=0}^{P-2}\frac{1}{j!},$$ where $j=P-2-k$. Now $\sum_{j=0}^{\infty}\frac{1}{j!}=e$, so $$(P-2)!\sum_{j=0}^{P-2}\frac{1}{j!}\approx(P-2)!e.$$ This will always be an overestimate, but it will be an overestimate by $(P-2)!\sum_{j=P-1}^{\infty}\frac1{j!}\approx\frac1{P-1}$, and in fact the error will always be less than $1$. So just rounding down to the next integer will give the right answer.