GATE 2024 CS (CS2) – Question 34

Engineering Mathematics · Discrete Mathematics: Sets, Relations, Functions, Partial Orders and Lattices · 1 mark · Numerical answer

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 __________

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: 5

Explanation

Count linear extensions with 1<2, 3<2, 3<4. Enumerating: 1,3,2,4; 1,3,4,2; 3,1,2,4; 3,1,4,2; 3,4,1,2. Total = 5.