GATE CS 2024 Set 2 — Question 34

A total order (or linear extension) containing $P$ must satisfy all the relations in $P$. The given relations (excluding reflexivity) are:We need to find the number of permutations of $\{1, 2, 3, 4\}$ that satisfy these conditions.Let's analyze the constraints:

• $3$ must precede both $2$ and $4$. Thus, $3$ must be placed before $2$ and $4$ in the sequence.
• $1$ must precede $2$.

Let's consider the possible positions for the element $3$:
Since $3$ must be before $2$ and $4$, $3$ can be at the 1st or 2nd position. It cannot be at the 3rd or 4th position because it needs at least two elements after it ($2$ and $4$).Case 1: $3$ is at the 1st position.
Sequence: $3, \_, \_, \_$
Remaining elements to place: $\{1, 2, 4\}$.
Constraint remaining: $1 < 2$.
We need to arrange $\{1, 2, 4\}$ such that $1$ appears before $2$. The total permutations of 3 elements is $3! = 6$. In exactly half of them, $1$ appears before $2$. So, $6/2 = 3$ valid permutations.
Alternatively, listing them:

• $1, 2, 4$ $\rightarrow$ Total order: $3, 1, 2, 4$
• $1, 4, 2$ $\rightarrow$ Total order: $3, 1, 4, 2$
• $4, 1, 2$ $\rightarrow$ Total order: $3, 4, 1, 2$

(Note: $2, 1, 4$; $2, 4, 1$; $4, 2, 1$ are invalid because $2$ precedes $1$).
So, there are 3 valid orders starting with $3$.Case 2: $3$ is at the 2nd position.
Sequence: $\_, 3, \_, \_$
For $3$ to be second, the first element must be something that doesn't require $3$ to be before it. The only element that doesn't require $3$ before it is $1$ (since $2$ and $4$ require $3$ before them). So, the first element must be $1$.
Sequence: $1, 3, \_, \_$
Remaining elements to place: $\{2, 4\}$.
Constraints remaining: None between $2$ and $4$. The constraints $1 < 2$, $3 < 2$, $3 < 4$ are all satisfied by the positions relative to $1$ and $3$.
Possible arrangements for $\{2, 4\}$:

• $2, 4$ $\rightarrow$ Total order: $1, 3, 2, 4$
• $4, 2$ $\rightarrow$ Total order: $1, 3, 4, 2$

So, there are 2 valid orders starting with $1$.Total Number of Total Orders:
$3$ (from Case 1) + $2$ (from Case 2) = $5$.The 5 valid total orders are: