Graph:
1 --> 4
2 --> 5
3 --> 6
My thoughts:
There are 3 choices for the first slot.
Then there are 3 choices for the second slot (Two remaining vertices with no dependents, and the dependent of the first picked node)
Then there are 2 choices for the third slot (If you pick the dependent of the first vertex, then you are left with two vertices with no dependents. If you pick one of the two vertices with no dependents, you are left with two vertices)
Then there are two choices for the fourth slot (I think?)
I get lost around here...
Is it 3 * 3 * 2 * 2?
What is the general way to calculate this?
Let me generalize to a similarly constructed digraph $G_n$ on $2n$ vertices. Then you have $n$ pairs of vertices, say $\{u_k,v_k\}$ for $k=1,\ldots,n$. A topological ordering of $G_n$ is a permutation of $V_n=\{u_k:k=1,\ldots,n\}\cup\{v_k:k=1,\ldots,n\}$ such that $u_k$ precedes $v_k$ for each $k\in\{1,\ldots,n\}$. Say that two permutations of $V_n$ are equivalent if they differ only by interchanges of $u_k$ and $v_k$ for $k$ in some subset of $\{1,\ldots,n\}$. This is clearly an equivalence relation on the set of permutations of $V_n$. $\{1,\ldots,n\}$ has $2^n$ subsets, so each equivalence class has cardinality $2^n$. Clearly each equivalence class contains exactly one topological ordering of $G_n$, so there are $\dfrac{(2n)!}{2^n}$ topological orderings of $G_n$. In particular, $G_3$ has $$\frac{6!}{2^3}=\frac{720}8=90$$ topological orderings, a figure that can be verified by only moderately tedious case-by-case computation. (I know, because I did it the hard way before I realized what was going on.)