How many paths are there in graph $K_n$? We know In $K_4$ there is $(4*3)+(4*3*2)+(4*3*2*1)$ paths in graph.
How many paths are there in graph $K_n$?
I want a simple formula...
 A: As you given for $K_4$, the answer is simply $n!(1+\frac{1}{2!}+\dots+\frac{1}{(n-2)!})= [n!e]-n-1$ for $n\ge 2$. The sum is computed as follows
$$
\begin{align}
&n!e-n!(1+\frac{1}{2!}+\dots+\frac{1}{(n-2)!}+\frac{1}{(n-1)!}+\frac{1}{n!})\\
=&\frac{1}{n+1}+\frac{1}{(n+1)(n+2)}+\dots\\
<&\frac{1}{n+1}e\\
<&1.
\end{align}
$$
A: In your proposed answer, you are counting directed paths.  E.g., the path of length $2$ from vertex $1$ to vertex $3$ is considered different to the path of length $2$ from vertex $3$ to vertex $1$.  Another e.g., this would imply $K_2$ has two paths.
Typically a path is considered to be undirected.  Thus, the answer will need to be divided by $2$ (since each undirected path is counted twice).
In general, the number of directed $k$-vertex paths ($k \geq 2$) in $K_n$ is $$n \times (n-1) \times \cdots \times (n-k+1),$$ this is the number of sequences of length $k$ without repeated entries.  Thus the number of undirected $k$-vertex paths is $$\frac{1}{2} n \times (n-1) \times \cdots \times (n-k+1).$$  So the total number of paths is $$\frac{1}{2} \sum_{k=2}^n n \times (n-1) \times \cdots \times (n-k+1).$$  Now we simplify to taste.  Personally, I already consider this a "simple formula" since it only involves $O(n)$ integer operations (addition, multiplication, and a single division operation).  But a simplification such as in Ma Ming's answer also works.
