Given a dag, how many distinct ways are there to topologically sort it? (A topological sort of a dag is a sequence of vertices of the dag such that if there is a path from u to v in the dag, then u appears before v in the sequence).

I don't know the answer. I was able to figure it out for the limited case of trees.

Consider the subtree of some vertex v. Suppose that v has n children and that we've already managed to sort the subtrees rooted at v's children. If the subtree of each child i has q_i distinct sortings, then we can choose a sorting for each of n children in \Pi_i{q_i} different ways. Given such a choice of n sortings, we want to know how many different ways there are to intertwingle them. To that end, think of each sorting of a child as a queue. To form an overall sorting of these $n$ sortings, we repeatedly choose a queue, remove its head element, and use that as the next element of the total order. The number of ways to do this depends, of course, on the sizes of the various queues.

Think of the sizes of the queues as a vector (q_1, q_2, q_3, ... q_n). Choosing a queue and popping its head is equivalent to reducing one co-ordinate of this vector by a unit.

Thus, the number of different ways to choose all the elements from all the queues is exactly the same as the number of minimal paths from (q_1, q_2, q_3, ... q_n) to the origin in an n-dimensional lattice. Let P(v) be the number of such paths from a vertex v. I'll build up a recursive computation for P(v) based on some examples below.

size(v) is the length of any minimal path from v to origin, which is also the sum of all the coordinates of v.

P(0) = 1

P(d, 0, ... 0) = 1 (if we are on an axis, there is only one path to the origin: along the axis)
P(d, 1, 0, ... 0) = d+1 (if we are one step off an axis, we must traverse that step, but we can do it at any point along the path parallel to the axis)
P(d, 1, 1, 0, ... 0) = (d+1)^2 (if we are two steps off an axis, in two different directions, then we must traverse each of those, and the choice of where to traverse them is independent)

[further details omitted until they can be corrected]