Ruined Weekend

Your weekend is ruined because your parents have reminded you of a number of chores to be completed. You can only do one chore at a time and some of them depend on others: for instance, you can make your bed only after you pick up all the books on the bed and put them away. Rather than start on the chores, you begin to calculate the number of ways you could reorder them to get them done, while ensuring that you do not violate any dependencies. For example, suppose you have four tasks to complete|for convenience, we assume the tasks are numbered from 1 to 4. Suppose that task 4 depends on both task 2 and task 3, and task 2 depends on task 1. One possible sequence in which we can complete the given tasks is [3,1,2,4] | in this sequence, no task is attempted before any of the other tasks that it depends on. The sequence [3,2,1,4] would not be allowed because task 2 depends on task 1 but task 2 is scheduled before task 1. In this example, you can check that there exactly three possible sequences compatible with the dependencies: [3,1,2,4], [1,2,3,4] and [1,3,2,4]. In each of the cases below, you have N tasks numbered 1 to N with some dependencies between the tasks. You have to calculate the number of ways you can reorder all N tasks into a sequence that does not violate any dependencies. Here the tasks numbered from 1 to 10 1 on nothing , 2 0n 1, 3 on 2 , 4 on 1 , 5 on 4 , 6 on 3 and 5 , 7 on 6 , 8 on 7 , 9 on 6 , 10 on 8 and 9