2
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Jul 14 '13 at 7:34
3
$\begingroup$

It needs only a minor correction.

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.)

$\endgroup$
2
  • $\begingroup$ Thanks very much for your answer. It is clear to me now. $\endgroup$ Jul 14 '13 at 7:44
  • $\begingroup$ @Daniel: You’re very welcome. $\endgroup$ Jul 14 '13 at 7:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.