How many paths of order $k$ are in the complete graph of order $n$ and the same question of a cycle of order $l$ in a complete graph of order $n$?

Question

So I'm looking for a formula with proof, but can't find one anywhere.

How many copies of paths of order $k$ are in the complete graph of order $n$ and the same question of a cycle of order $l$ in a complete graph of order $n$?

Answer 1

Since the graph is complete, given any ordered list of $k$ distinct points $v_1, \ldots, v_k$ there exists a path between them. So we just need to count ordered lists. There are $n$ ways to choose the first point, $(n - 1)$ ways to choose the second, and so on. However we don't care about the direction we list the path in, so we over count by a factor of 2. Therefore the total number of paths of length $k$ is $$ \#\text{paths of order $k$} = \frac{n \times (n - 1) \times \cdots \times (n - k + 1)}{2} = \frac{n!}{(n-k)!\times2} $$ Similarly for a cycle, any ordered list of $l$ points forms a cycle. However for a cycle, we don't care about direction or the start point. Therefore by counting ordered lists of vertices, we over count by a factor of $2 l$ ($l$ different choices for the start point, 2 choices for direction). So the number of cycles of length $l$ is given by $$ \#\text{cycles of order $l$} = \frac{n \times (n - 1) \times \cdots \times (n - l + 1)}{2l} = \frac{n!}{(n-l)!\times 2l}$$