Let P be the partial order defined on the set \1, 2, 3, 4\ as follows P = \(x, x) x ∈ \1, 2, 3, 4\\ \(1, 2), (3, 2), (3, 4)\ The number of total orders on \1, 2, 3, 4\ that contain P is __________

GATE CSE 2024 Session 2 Q34: Total orders extending a given partial order on {1,2,3,4}

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

$P = \{(x, x) \mid 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 __________

Try it: numerical answer: type the value

Your answer

Numerical answer. No negative marking.

Show answer and explanation

Answer: 5 (official GATE 2024 final answer key)

Concept used: Counting linear extensions (topological sorts) of a poset.

First step: Constraints are $1 < 2$ , $3 < 2$ , $3 < 4$ ; the first element must be 1 or 3, then branch.

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

Source: official GATE 2024 Session 2 CS question paper and final answer key, organised by IISc Bangalore. Question paper · Answer key