2

I stumbled across this question when i was practicing for indian zonal informatic olympiad need some hint to solve this question:

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 $2 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.

image contains the cases to be solved

Asaf Karagila
  • 393,674
Aman Gandhi
  • 41

1 Answers1

1

Here is the digraph for the first case:

enter image description here

As we can notice if a sequence works it must be as follows:

$1,X,X,X,X,6,?,?,?,10$

The symbols $?,?,?$ must be a permutation of $7,8,9$ such that $7$ comes before $8$. There are $3$ of those.

The symbols $X,X,X,X$ must be a permutation of $2,3,4,5$ such that $2$ goes before $4$ and $4$ comes before $5$, there are $4!/4=6$ of those.

Therefore there are $18$ permutations in total.

The digraph for the last one is:

enter image description here

So the sequence must be:

$?,?,?,4,X,X,7,Y,Y,Y,Y,Y,Y,14,15$.

Here $?,?,?$ can be any permutation of $1,2,3$ so there are $6$ options.

$X,X$ can be any permutation of $5,6$ so there are $2$ options.

$Y,Y,Y,Y,Y,Y$ must be a permutation of $8,9,10,11,12,13$ so that $8,9,10$ appear in that order and $11,12,13$ appear in that order. It is not hard to see there are $\frac{6!}{3!^2}=20$ such permutations.

Hence the final answer is $6\times2\times 20=240$.

Asinomás
  • 105,651