Reference for counting the number of paths in a DAG
This idea is sufficiently well-known that I'm pretty sure I've seen papers just say things like &quot;we can count the number of paths by dynamic programming&quot; and stop there, with the expectation that the reader can fill in the details.
It is also the semiring problem for $\mathbb{N}$ with the usual $+$ and $\times$, and can be extended to cyclic graphs by extending the value set to $\mathbb{N} \cup \infty$ and adding a suitable $a^*$ operator.