Number of paths of length $P_{n-1}$ in $K_n$? Question:
Let $K_n$ be the complete graph on n vertices and $P_m$ be a path on m vertices where m = n - 1. How do you calculate the number of copies of $P_m$ in $K_n$?
Where I am at so far
All I know is that that there are 3 copies of $P_2$ in $K_3$. 
 A: Your title says $P_{n+1}$ but your question asks for $P_{n-1}$.
Assuming you are going for non-intersecting paths only. Consider a path with $n-1$ vertices. Once you fix the first vertex and the last vertex of the path, the remaining $n-3$ vertices can be put in different orders to create a unique path with each arrangement.
So the number of such paths is:
$$\underbrace{\binom{n}{2}}_{\text{A}}\underbrace{\binom{n-2}{n-3}}_{\text{B}}\underbrace{(n-3)!}_{\text{C}}=\frac{n!}{2},$$
where


*

*A is no. of ways of choosing first and last vertex.

*B is no. of ways of choosing in between vertices.

*C is no. of ways of arranging the in between vertices.


In fact this idea can be generalized to paths with $m$ vertices.
$$\underbrace{\binom{n}{2}}_{\text{A}}\underbrace{\binom{n-2}{m-2}}_{\text{B}}\underbrace{(m-2)!}_{\text{C}}=\frac{n!}{2(n-m)!}.$$
A: Because any pair of vertices in $K_n$ is connected by an edge, any sequence of $n-1$ distinct vertices corresponds to a path. There are $n!$ such sequence because you have $n$ choices for the first vertex, then $n-1$ choices for the second, then $n-2$ choices for the third, etc, and finally $2$ choices for the last vertex. Each path has two orientations, so every path corresponds to precisely two such sequences, so the total number of paths is $\tfrac{n!}{2}$.
By the same argument, the number of paths of length $m$ in $K_n$ equals $\tfrac{n!}{2(n-m)!}$ for $m>1$.
