Q: Copies of $P_m$ in $K_n$ and $C_m$ in $K_n$ $P_m$ in $K_n$ (not ethat $P_m$ has $m$ edges and $m+1$ vertices.: First pick the $m+1$ vertices of the path from the $n$ vertices of the complete graph. This gives $\binom{n}{m+1}$. Then order the vertices in $(m+1)!$ ways. However, we have overcounted by twice as many, so divide by $2$ to give $\frac{\binom{n}{m+1}(m+1)!}{2}$.
If this is right, my question is how do I justify dividing by $2$?
$C_m$ in $K_n$: First, pick the $m$ verties of the cycle from the $n$ vertices of the complete graph. This gives $\binom{n}{m}$. There are $m!$ ways to order the vertices. However, we must divide by $2 \cdot m$ as we can rotate the cycle in both the clockwise and anti-clockwise direction in $m$ ways to give the same cycle. In all: $\binom{n}{m}2 \cdot m$.
Is this correct?
