Directed Acyclic Graph of

Question

I have the solution to a word problem, which seems like a directed acyclic graph and I do not see how the author came up with the edges they did. The problem is if Tie can be worn after shirt. Socks after trousers and shirt. Shoes can be worn after socks. Belt can be worn after socks. How many different paths are there? Can someone provide the graph with nodes numbered from 0 - 5 for each event? The edges I have as the answer are 5-2, 5-0, 4-0, 4-1, 2-3, 3-1

Answer 1

The answer is that there are only six possible orderings. The key is that the socks have three items that must precede them, and two that must come after them.

So for each ordering of Tie, Shirt and Trousers, there are two distinct "paths", because the shoes can come before or after the belt; there is no other freedom because both are stuck being after the socks.

Now there are $3!=6$ conceivable orders for Tie, Shirt and Trousers, because they are stuck coming before the socks. Of those six conceivable orders, three must be discarded because they had shirt after tie.

So the total number of paths is $2\times 3 = 6$.