Paths starting from a given node that touch each node a given number of times How many paths starting from a given node touch each node a given number of times?
We have a complete graph with vertices $1,2,3…j$. We want to know the number of paths of length $N$, starting from vertex $1$, such that vertex $i$ appears $k_i$ times for $1≤i≤j$. $N$ is equal to the sum of the $k_i$'s.
For the case with arbitrary initial vertex, the answer has been provided elsewhere on this forum (see Find the number of arrangements of $k \mbox{  }1'$s, $k \mbox{  }2'$s, $\cdots, k \mbox{  }n'$s - total $kn$ cards.) 
 A: This can be solved using the Goulden-Jackson cluster method; see Noonan-Zeilberger.  We will assume some notation and terminology from this paper.
We start by giving an alternate solution to the problem with arbitrary initial vertex; it's then a short hop to address the issue of a fixed initial vertex. Let $\mathcal{L}$ denote the language over the alphabet $\{1,\ldots,j\}$ having no repeated symbols (so the "forbidden words" are $11, 22, \ldots, jj$.  We want to count words in $\mathcal L$ of length $N=k_1+\cdots+k_j$ having $k_i$ occurrences of $i$.  Using the Goulden-Jackson cluster method, this count is the coefficient of $a_1^{k_1}\cdots a_j^{k_j}$ in $$ m = \frac{1}{1 - (a_1+\cdots+a_j) + \frac{a_1{}^2}{a_1+1}+
  \cdots+\frac{a_j{}^2}{a_j +1}}.$$
In the terminology of Noonan-Jackson, $-a_i{}^2/(a_i+1)$ is the weight enumerator of the set $\mathcal{C}[i]$ of marked clusters beginning with $i$. (If you want to tag the length of the word as well, replace each $a_i$ with $a_i t$.)
Now, let $\mathcal{L}_1$ be the language consisting of words in $\mathcal{L}$ beginning with $1$.  $\mathcal{L}_1$ can be partitioned into two sets: those words in which the initial $1$ is part of a cluster, and those in which it is not.  The resulting decomposition is
$$ \mathcal{L}_1 = \{1\}\, \mathcal{L}\:\cup\: \mathcal{C}[1]\,\mathcal{L}$$
which yields the weight enumerator for $\mathcal{L}_1$:
$$ m_1 = \left(a_1 - \frac{a_1{}^2}{a_1+1}\right) m,$$
where $m$ is as above.
As an example, suppose $j=3$, $k_1=2$, $k_2=4$ and $k_3=3$ (so $N=9$).  Expanding the series, we see that the coefficient of $a_1^2 a_2^4 a_3^3$ is $13$. This agrees with the direct count, as computed (e.g.) in Mathematica:
ok[s_] := And @@ (Unequal @@ ## & /@ Partition[s, 2, 1]);
Select[Permutations[{1, 1, 2, 2, 2, 2, 3, 3, 3}], ok[#] && #[[1]] == 1 &] // Length
> 13

