GATE 2024 CS2 Q.34: solution and answer

GATE 2024 · CS2Q.34 · 1 mark · NAT

Let $P$ be the partial order defined on the set ${1, 2, 3, 4}$ as follows

P = {(x, x) ∣ x \in {1, 2, 3, 4}} \cup {(1, 2), (3, 2), (3, 4)}

The number of total orders on ${1, 2, 3, 4}$ that contain $P$ is __________

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The number of total orders on ${1, 2, 3, 4}$ that contain $P$ is $5$ .

Official answer: 5Source: Official answer key, GATE 2024 CS2 (IISc Bengaluru)

A total order containing $P$ is a linear extension of $P$ : a listing of $1, 2, 3, 4$ in which, for every pair $(a, b) \in P$ with $a \neq = b$ , $a$ comes before $b$ . The reflexive pairs $(x, x)$ impose no condition.
The non-reflexive pairs give three constraints: $1$ before $2$ , $3$ before $2$ , and $3$ before $4$ . The Hasse diagram is a zigzag $1 < 2 > 3 < 4$ .
Only $1$ and $3$ have nothing forced before them, so the first element of the listing is $1$ or $3$ .
Case first $= 1$ : the remaining elements are $2, 3, 4$ . Both $2$ and $4$ must come after $3$ , so $3$ comes next. The last two places hold $2, 4$ in either order. This gives $1, 3, 2, 4$ and $1, 3, 4, 2$ , which is 2 orders.
Case first $= 3$ : the remaining elements are $1, 2, 4$ and the only constraint left is $1$ before $2$ , with $4$ unconstrained. Of the $3! = 6$ arrangements of ${1, 2, 4}$ , exactly half, 3, have $1$ before $2$ : $3, 1, 2, 4$ ; $3, 1, 4, 2$ ; $3, 4, 1, 2$ . This is 3 orders.
Total $= 2 + 3 = 5$ . Check: the two cases are disjoint and every valid listing starts with $1$ or $3$ , so no order is missed or counted twice.

KEY IDEA

Total orders containing a partial order are its linear extensions. Count the permutations that respect every non-reflexive pair, splitting by which element can come first.

WATCH OUT FOR

Counting all $4! = 24$ permutations, or forgetting that a total order must keep $P$ 's pairs in the same direction, so $3$ must precede both $2$ and $4$ and $1$ must precede $2$ . Another slip is to treat the reflexive pairs as constraints, or to miss that $4$ is free once $3$ is placed.

From the GATE 2024 CS2 paper. Every question of this paper · Download the full paper · All 8 Sets & relations questions, with notes

GATE 2024 CS2 Q.34: solution and answer

Answer and solution

More Sets & relations questions