maximum possible number of paths in an acyclic digraph I have been trying to find a general formula for the maximum possible number of paths in an acyclic digraph.  The method I used was to simply draw several differently sized digraphs with the maximum amount of links, count each path and see if I noticed any patterns.
Here is what I found:

The pattern I noticed is that the maximum possible paths from "start" to "end" seems to be equal to $ 2^{n-2} $, where n = number of nodes in the digraph.  I was wondering if anyone could possibly explain a more mathematical approach to solving this problem.
 A: Notice that every subset of nodes containing start and end gives a path from start to end and vice verse. So, the number of paths is the same as the number of subsets. To get a subset containing start and end just pick any subset that contains neither of those nodes and then add them. That means picking a subset of a set of $n-2$ nodes, but the total number of those subsets is $2^{n-2}$. Thus, the number of paths is  $2^{n-2}$
A: 1- Finding the Number of Subsets of a Set
Let's start with stating the obvious: Every path from start to end must contain the start and end nodes and can include as many or as less nodes in between. In other words, its a given that the start and end nodes are included in the path, so we play around with the remaining (N-2) nodes. In set theory lingo that translates to: For a DAG that has N-2 intermediate nodes. Any number of these nodes can be included. How many different paths are possible?
C(N-2, 0) + C(N-2, 1) + C(N-2, 2) + C(N-2, 3) + ....... + C(N-2, N-2)
For simplicity, let n = N-2
C(n, 0) = How many ways we can choose zero intermediate nodes between start and end = n!/(n-k)! * k! = n!/(n! * 0!) = 1
C(n, 1) = How many ways we can choose 1 intermediate nodes between start and end ... etc
Below is a visual illustration of the possible paths for a sample DAG:
visual explanation 1
2- Children and chairs
Another way to find the upper limit mathematically is as follows:
For each one of the intermediate nodes (excluding start and end node) there is one of two options: Either be part of the path, or no. This can be expressed as follows: If we have 3 intermediate nodes, we can treat them as chairs.
2 * 2 * 2 = 2^3 = 8 paths
visual description 2
K = number of paths = 2^(N-2)
Time comlexity = E + k*V = E + 2^(N-2)*V, where E = number of Edges, V = number of vertices
