Finding paths of certain length in trees
Idea: Root the tree in an arbitrary node. For every node, count 


paths in its subtrees,
paths that start in a subtree and end in the root, and
paths that start in one subtree, traverse the root and end in another subtree.


That is, for a given node $v$ with children $u_1, \dots, u_m$, the number $p(v,k)$ of paths of length $k$ (counting nodes) in the subtree $T_v$ rooted in $v$ is

$\qquad\displaystyle\begin{align*}
  p(v,k) &amp;= \sum_{i=1}^m \biggl[ p(u_i,k) \biggr] \\
         &amp;\ + \sum_{i=1}^m \biggl[ p_r(u_i,k-1) \biggr] \\
         &amp;\ + \sum_{i=1}^{m-1}  \sum_{j=i+1}^m \sum_{l=1}^{k-2} \biggl[ p(u_i,l) \cdot p(u_j,k-1-l) \biggr] 
\end{align*}$

for $k \geq 2$; we anchor the recurrence in $p(v,1) = 1$ for all $v$. For the paths ending in the root, we get the (simpler) recurrence

$\qquad\begin{align*}
  p_r(v,k) &amp;= \sum_{i=1}^m p_r(u_i,k-1)
\end{align*}$

which also anchors in $p_r(v,1) = 1$. 

These recurrences immediately imply a recursive algorithm (computing both simultaneously). 

The runtime is in "$\Theta(m^2k)$" per node of degree $m$; hence, on trees with finitely bounded degree, the algorithm runs in time $\Theta(nk)$. Otherwise, it may take time $\Theta(n^2k)$ (e.g. on stars).