Total number paths between two nodes in a complete graph 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?
 A: The number of paths with $k$ edges ($1\le k\le P-1)$ between two
distinct vertices in the complete graph $K_P$ is
$$(P-2)(P-3)\cdots(P-k)=\frac{(P-2)!}{(P-k-1)!}$$
so the total number is
$$(P-2)!\left(\frac1{(P-2)!}+\frac1{(P-3)!}+\cdots
+\frac{1}{1!}+1\right).$$
The bracket is very close to $e$.
A: Firstly, we should be precise: the formula $\lfloor (P-2)! e \rfloor$ holds only for $\boldsymbol{P \ge 3}$. This, an addition to the floor operation, suggests that the formula's correctness relies on some approximation.
As Especially Lime's answer explains, the actual number of paths is
$$
\sum_{i=0}^{P-2} \frac{(P-2)!}{i!}.
$$
Now, to prove that for some integer $x$ and real number $y$, $x = \lfloor y \rfloor$, one shows that $x \le y < x + 1$.
So what we formally need to show is
$$
\sum_{i=0}^{P-2} \frac{(P-2)!}{i!} \le (P-2)!e < \sum_{i=0}^{P-2} \frac{(P-2)!}{i!} + 1.
$$
Expand $e$ as $\sum_{i=0}^\infty \frac{1}{i!}$ and we get:
$$
\sum_{i=0}^{P-2} \frac{(P-2)!}{i!} \le \sum_{i=0}^\infty \frac{(P-2)!}{i!} < \sum_{i=0}^{P-2} \frac{(P-2)!}{i!} + 1.
$$
Subtracting terms $0$ to $(P-2)$ from all three terms of the inequality, we need to show that
$$
0 \le \sum_{i=P-1}^\infty \frac{(P-2)!}{i!} < 1.
$$
The first part of the inequality is true because all terms are nonnegative, i.e. $(P-2)! \ge 0$. For the second part of the inequality,
we have
\begin{align*}
\sum_{i=P-1}^\infty \frac{(P-2)!}{i!}
&= \frac{1}{(P-1)} + \frac{1}{P(P-1)} + \frac{1}{(P+1)P(P-1)} + \cdots \\
&< \frac{1}{P-1} + \frac{1}{P(P-1)} + \frac{1}{(P+1)P} + \frac{1}{(P+2)(P-1)} + \cdots \\
&= \frac{1}{P-1} + \left( \frac{1}{P-1} - \frac{1}{P} \right)
  + \left( \frac{1}{P} - \frac{1}{P+1} \right)
  + \cdots \\
&= \frac{2}{P-1} \qquad \text{(telescoping)} \\
&\le 1 \qquad \qquad \text{(since } P \ge 3 \text{)}.
\end{align*}
This completes the proof.
A: 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.
