Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

If G is a complete graph on n vertices and u,v,w are three distinct vertices in the vertex set of G, then how many different paths are there from u to v passing through w?

For 3 vertices it is simple, each vertex has degree 2, one of the edges leading directly v - so there is only 1 path.

For 4 vertices, it looks as if there are 3 distinct paths going through any fixed vertex w.

For 5 vertices it is becoming tricky and since there are 3 edges not going directly to v, but they can go to each other... well I have counted at least 8 distinct paths so far and am thinking maybe that is correct - that somehow maybe for 3 vertices, there is one edge not going directly to v, and (inventing a relation) 1^2 - 1 = 1 which is true. For 4 vertices it would be 2 distinct edges not going to v so 2^2 - 1 = 3 which works. Then for 5 vertices, the 3 distinct edges not going to v would give me 3^2 - 1 = 8.

So in general I could come up with a formula of $$(n-2)^{2} -1.$$ But this is a shot in the dark and I have no idea. Any thoughts?

Thanks,

Brian

share|improve this question

1 Answer 1

up vote 4 down vote accepted

Let $p_n$ denote the total number of paths between $u$ and $v$ through some $w$. Your path can have anywhere between $3$ and $n$ vertices. If your path has $k$ vertices, then there are $k-3$ choices of intermediate vertices from the $n-3$ free vertices together with $(k-2)!$ choices of rearrangements. Therefore in total we have $$p_n=\sum_{k=3}^n\binom{n-3}{k-3}(k-2)! = \sum_{k=3}^n\frac{(n-3)!}{(n-k)!}(k-2)$$ This is essentially the formula, but there is a "closed form" in terms of the incomplete gamma function if you want.

We rewrite the sum with $\ell = n-k$ as $$p_n=(n-3)!\sum_{\ell=0}^{n-3}\frac{n-\ell-2}{\ell!}=(n-2)!\sum_{\ell=0}^{n-3}\frac{1}{\ell!}-(n-3)!\sum_{\ell=0}^{n-4}\frac{1}{\ell!}$$ Each of the summands can be expressed in terms of the incomplete gamma function, namely $$k!\sum_{\ell=0}^{k-1}\frac{1}{\ell!} = ek\Gamma(k,\ 1)=ek(k-1)\Gamma(k-1,\ 1) + k$$ where $e$ is the base of the natural logarithm and $\Gamma(k,\ 1)$ is the incomplete gamma function. Using the above, we can simplify as $$\begin{align}p_n &= e(n-2)\Gamma(n-2,\ 1)-e(n-3)\Gamma(n-3,\ 1) \\&=e(n-2)(n-3)\Gamma(n-3,\ 1)-e(n-3)\Gamma(n-3,\ 1) + n-2 \\&=e(n-3)^2\Gamma(n-3,\ 1)+n-2\end{align}$$

The sequence begins from $n=3$ as $$1,\ 3,\ 11,\ 49,\ 261,\ 1631,\ \cdots$$

share|improve this answer
    
Holy Cow! I was way off! Thanks EuYu. I don't think the instructor ever even mentioned that there was a Gamma function involved in anything in the class - so it didn't even come to mind, I will have to look it up. I appreciate your time, thanks again. –  Relative0 May 13 '13 at 9:28
1  
@user1922184 The incomplete gamma is not truly necessary. It just gives a tidy way for expressing the formula. The sum given in the first line is sufficient if you're unfamiliar with the gamma. –  EuYu May 13 '13 at 9:32
    
Thanks again EuYu. I am wondering two things. First, as you said "Your path can be anywhere between length 3 and length n", what about those paths that are u -> v -> w as those have length 2, or is since there is only 1 of those (directly from u to v to w) that is just one choice? Also, for (k-2)! choices of re-arrangements is that because there is whatever path was used to come to v as well as a single path directly from v to w which gives us k-2 other paths? –  Relative0 May 14 '13 at 5:54
    
@user1922184 Ah, I was referring to the length as in the number of vertices. I probably should have mentioned that. The $(k-2)!$ rearrangements comes from permuting the central vertices of the path. If there are $k$ vertices in your path then there are $k-2$ central vertices (excluding the endpoints $u$ and $v$). These $k-2$ central vertices can be permuted anyway you want, giving $(k-2)!$ rearrangements. –  EuYu May 14 '13 at 6:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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