In math contests, such as those run by the University of Waterloo CEMC in Canada or the AMC series of contests in the US, there are frequently questions of the following kind:
Given an $m\times n$ grid, how many paths are there from the bottom-left corner to the top-right corner that can go only up or right? (Classic)
The above is a well-known problem where writing the number of paths between the bottom-left corner and any other vertex corresponds to a rotated version of Pascal's triangle of binomial coefficients. Other variations include a $3D$ version with a rectangular prism, and another where you can only travel on the surface of the prism. A recent contest problem is:
A frog is positioned at the origin of the coordinate plane. From the point $(x, y)$, the frog can jump to any of the points $(x + 1, y)$, $(x + 2, y)$, $(x, y + 1)$, or $(x, y + 2)$. Find the number of distinct sequences of jumps in which the frog begins at $(0, 0)$ and ends at $(4, 4)$. ($2018$ AIME II)
Pascal's method works in this problem: put a $1$ at the origin and fill in each "successive" vertex by adding the numbers at all vertices that leads to it. A directed graph on which this method works appeared on the 2004 Pascal Contest (problem $21$), and I am sure that I have come across numerous other examples.
What I have pondering for some time are the following two questions:
Is there a neat classification of directed graphs for which Pascal's method works for finding the number of paths from a given origin to a desired destination?
What about directed graphs where Pascal's method works for any origin vertex and any destination vertex?
Not all directed graphs can work because, for example, the existence of a cycle might lead to infinitely many possible paths from the given origin to the desired destination. We can assume that there are no loops or multiple edges between one pair of nodes. A finite number of vertices might not be needed, as shown by extending the first classic example to an infinite grid corresponding to the first Cartesian quadrant.
You have already noticed that if there is a cycle, then we are in trouble. However, if the directed graph is acyclic, then we are always fine. First, find a topological ordering of the directed graph. Then, apply the "Pascal method" for counting paths to each vertex, going through the vertices in that order. (Label the starting vertex with a $1$, all vertices that precede it with a $0$, and then label each vertex $v$ you get to with the sum of the labels on the vertices that have edges to $v$.)
In such a graph, we can use the method for any starting vertex and any destination. If we specifically want to start from $s$ and end at $t$, we can only weaken this a little. Let $A$ be the set of all vertices that can be reached from $s$ (including $s$ itself). Let $B$ be the set of all vertices that can reach $t$ (including $t$ itself). Then it's enough to solve the problem on the subgraph induced by $A \cap B$, and so it's enough for this subgraph to be acyclic: if there are cycles elsewhere, that's fine.