I'm trying to find a succinct and general way to count the number of paths in a directed graph with only tree edges (assuming all nodes have exactly the same number of children).
For example, the picture below has
- 8 3-length paths
- 12 2-length paths
- 14 1-length paths
For a total of 34 paths.
I can calculate that number by evaluating the number of paths to each leaf node then subtracting double-counted paths at shallower depths. E.g.,
paths(n) = n*(n+1)/2
nodes(depth, breadth) = breadth^depth
paths(3)nodes(3,2) - paths(2)nodes(2,2) - paths(1)nodes(1,2)
= paths(3)8 - paths(2)4 - paths(1)2
= 6*8 - 3*4 - 1*2
= 34
However, that approach only works for trees of depth 3, and is repetitive. Is there a formula to calculate that number that generalizes to trees of any depth?
I considered an approach with combinations/permutations, but haven't gotten a correct solution yet.
Best Answer
The parent node is level $0$. Define level $1$ as the $n$ child nodes below level $0$. Let $k$ be the number of levels. The $k$th level introduces $n^k$ nodes. From each node at level $j$, if $j+p \leq k$, there are $n^p$ paths of length $p$; otherwise no such paths exist as there are not enough levels below. The total number of paths of length $p$ from the $j$th level is $n^jn^p = n^{j+p}$.
Define $f(n, k)$ as number of paths up to level $k$. The formula is
$$f(n, k)=\sum_{j=0}^{k-1}\sum_{p=1}^{k-j}n^{j+p} = \sum_{j + p \leq k} n^{j+p}$$
$f(n, 1) = n$
$f(n, 2) = 2n^2 + n$
$f(n, 3) = 3n^3 + 2n^2 + n$. Note that $f(2, 3) = 34$. An alternative view of the formula is there are $k$ ways to write $k$ as sum of $j + p$, where $j \in \{0, 1 \dots k - 1\}, p \in \{1, 2 \dots, k\}$. Similarly for each $p \leq k$ there are $p$ such ways.
The formula can be thus rewritten as $\displaystyle \sum_{p=1}^k{pn^p}$. According to Wolfram Alpha,
$$f(n,k) = \frac{n(k n^{k + 1} - (k + 1) n^k + 1)}{(n-1)^2}$$