Graph theory: Finding the number of different paths through a vertex on a complete graph 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
 A: 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$$
