Counting Topological Sorts Of Graph With In Degree 1 I was asked this question recently and am struggling to come up with the closed form solution: How many topological sorts are there for a directed acyclic graph where each vertex only has one incoming edge?
For a vertex whose children are all leaf nodes, the Number of Topological Sorts is $NTS(root) = |l|!$ where $l$=number of leaf nodes. E.g.
  1
 /|\
2 3 4

Should be $3!$: {1->2->3->4, 1->2->4->3, 1->3->2->4, 1->3->4->2, 1->4->2->3, 1->4->3->4}.
Also, if we look at a binary tree, whose right child is a leaf, we can see that the recurrence relation $NTS(root) = (NumNodes(root.left) + 1) * NTS(root.left))$. E.g.
    1
   / \
  2   5
 / \
3   4

The reasoning here is that for each topological sort starting at 2, we have a graph of the from a->b->c, that must contain all nodes reachable from 2. Then we can place the node 5 in any position in that graph and still have a valid topological sort: {1->5->a->b->c, 1->a->5->b->c, 1->a->b->5->c, 1->a->b->c->5}. This can be done for all permutations of the topological sort starting a 2. Thus $(NumNodes(root.left) + 1) * NTS(root.left)$. 
However, I am getting stuck on generalizing the binary tree case with a larger right subtree or to the n-degree tree cases.
 A: This is a nice problem.  I don't have the patience to do it right now, but I think I know how to go about it.  I'll give you my thoughts, and let you fill in the details.
I think you're on the right track.  We'll have to settle for a recursive answer.  Also, I think the crucial case is a binary tree $T$ consisting of root and two nonempty subtrees $L$ and $R$ with $\ell$ and $r$ elements respectively.  
If we are given a topological sort of $T$, the root comes first.  If we extract the elements of $l$ in order, they constitute and topologic sort of $L$, and similarly for the elements of $R$.  The question is, in how many ways can we blend a topological sort of $L$ with a topological sort of $R$?  Say we have two such sorts, $s_L$ and $s_R$.  We can take the first few elements of $s_L$, follow them with the first few elements of $s_R$, then add the next few elements of $s_L$, and so on.  Of course, we can also start with some some elements of $s_R$ instead.
How many ways are there to cut $s_L$ into $k$ nonempty chunks?  If we think of $s_L$ arranged in a line, there are $\ell-1$ spaces between the lines and we must choose $k-1$ of them, so $\binom{\ell-1}{k-1}$.  We must either split $s_L$ and $s_R$ into the same number of chunks, in which case we have two choices of which chunk to start with, or the number of chunks will differ by $1$, and there is only one choice of which chunk to start with.  For a given value of $k$ we get $$
2\binom{\ell-1}{k-1}\binom{r-1}{k-1} + \binom{\ell-1}{k-2}\binom{r-1}{k-1}+\binom{\ell-1}{k-1}\binom{r-1}{k-2}$$
We must sum this over all possible values of $k$.  $k$ must be at least $1$ and it cannot exceed $1+\min\{\ell,r\}$  Finally, we must multiply this number by $TS(L)TS(R)$ where $TS$ is the function that counts topological sorts.
If there are more than two children of the root, we simply continue. If there is a third child $U$, for example, with $u$ elements, we need to insert a topological sort of length $u$ into a topological sort of length $\ell+r$, so we can use the same procedure.
I have no idea whether the sum of products of binomial coefficients constructed above can be simplified. 
