# How many distinct copies of $P_m$ are in $K_n$?

Let $K_n$ be the complete graph of order $n$ and $P_m$ a path with $m$ distinct vertices, $1 \leq m \leq n$.

Question: How many distinct copies of $P_m$ are contained in $K_n$?

Given that a permutation maps a path to a different path it seems like there will always be another permutation which will send the original path to the same path, different from the original, so that the number of copies of $P_m$ contained in $K_n$ will be:

$$\frac{m!}{2}\binom{n}{m}$$

Is this correct? If not, or if so, could someone provide a more rigorous derivation of the correct value?

• Choose the $m$ vertices involved in the path. Then count how many ways there are to order those vertices into a path. Your formula seems right to me. Jul 14 '13 at 7:34

Any $m$ vertices of $K_n$ may be the vertices of a copy of $P_m$, so there are $\binom{n}m$ ways to choose the vertices of the path. They may be traversed in any order, so a given set $m$ vertices may be traversed as a path in $m!$ ways. However, for $m>1$ this overcounts by a factor of $2$, since it counts as distinct the two directions in which a copy of $P_m$ may be traversed. Thus, the number of copies of $P_m$ in $K_n$ is
$$\frac{m!}2\binom{n}m=\frac{n!}{2(n-m)!}=\frac12n^{\underline{m}}$$
if $m>1$ and $n$ if $m=1$. (Here $n^{\underline{m}}$ is the falling factorial.)