Number of DAGs of order $n$ whose longest path has $k$ vertices Fix a set $V$ of cardinality $n$. I'm trying to determine the number of possible DAGs (directed acyclic graphs) whose vertex set is $V$ with a longest path containing $k$ nodes, which I will write as $D^n_k$. 
So far, I have
$$ D^n_k = {n \choose k} (\ldots) $$
The $n \choose k$ is required because we have to choose the vertices which form the longest path. I also know that the part in the parentheses needs to give the number of possible subgraphs of order $n - k$ which don't extend the path to more than $k$ vertices, but I don't know how to even describe this. Although I am after a closed form, a recurrence, or help in obtaining one, would be very helpful for me.
 A: (Too long for a comment, not a full answer)
If we forget about the $k$ parameter and just look at the number of DAGs on $n$ labeled nodes then the total number of DAGs is given by the recurrence
$$ D_n = \sum_{k=1}^n(-1)^{k-1}\dbinom{n}k2^{k(n-k)}D_{n-k}.$$
If the nodes are not labeled, just divide by $n!$. This is also the OEIS sequence A003024. The first few numbers are $$1, 1, 3, 25, 543, 29281, 3781503, 1138779265, 783702329343, 1213442454842881, 4175098976430598143, 31603459396418917607425$$
so $D_n$ grows very quickly. As a very crude bound, if we only take the first term in the sum we get 
$$ D_n \approx 2^nD_{n-1}$$ so $D_n \approx 2^{n^2}$ (It grows even faster than this). 
If we make the bad assumption that all longest path lengths are equally likely, then the number of DAGs on $n$ labeled nodes with longest path having length $k$ is roughly $\frac{D_n}k.$ However, some longest paths are much more likely than others. More precisely, 

If we randomly pick a DAG out of all possible $D_n$ DAGs, what is the
  expected length of the longest path ?

If we forget about labels, and also orientation of the edges, it is plausible to believe that the question is roughly the same as asking 

If we randomly pick a tree out of all possible trees with $n$ vertices, what is the height of the tree?

This question has been answered here and the expected height is roughly $O(\sqrt{n}).$ Thus, for $k$ far away from $O(\sqrt{n})$, there might be much less than $D_n/n$ possibilities.
