Let $G = (N, A)$ be a connected acyclic digraph (DAG). Furthermore, let $s \in N$ and $t \in N$ be two vertices on this graph, such that $t$ is reachable from $s$.
My problem is: how many simple $s-t$ paths exist on this DAG?
Most precisely, how can we write a function on the number of nodes $|N|$ which is an upper bound for the number of simple $s-t$ paths in $G$?
I'm aware that exists a polynomial-time dynamic programming algorithm that counts the number of such paths (see here) and that is an enumeration problem. This algorithm is #P-Complete on general digraphs, but is in $P$ for DAGs, as pointed out by @Joshua Grochow in the comments.
I'm also aware that this number is exponential on the size of the longest $s-t$ path.
However, I don't see a relation between this function and the number of nodes in the graph.
Thanks in advance :)