GATE 2024 CS (CS2) – Question 34
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.
More Discrete Mathematics: Sets, Relations, Functions, Partial Orders and Lattices questions
- GATE 2023 CS Q49
- GATE 2021 CS (CS1) Q53
- GATE 2020 CS Q27
- GATE 2019 CS Q31
- GATE 2019 CS Q64
- GATE 2018 CS Q37
All Discrete Mathematics: Sets, Relations, Functions, Partial Orders and Lattices questions →