Let 𝑃 be the partial order defined on the set {1,2,3,4} as follows 𝑃 = {(𝑥,…
2024
Let 𝑃 be the partial order defined on the set {1,2,3,4} as follows
𝑃 = {(𝑥, 𝑥) | 𝑥 ∈ {1,2,3,4}} ∪ {(1,2), (3,2), (3,4)}
The number of total orders on {1,2,3,4} that contain 𝑃 is __________
Attempted by 177 students.
Show answer & explanation
Correct answer: 5
Key idea: count the linear extensions (topological sorts) of the poset. At each step pick a minimal element (an element with no predecessors among the remaining elements) and branch on the choices.
Initially the minimal elements are 1 and 3, so the first element in a linear extension must be either 1 or 3.
Case: first element is 1
After placing 1, the only minimal element is 3 (both 2 and 4 require 3). So the second element must be 3.
After 1 and 3 are placed, the remaining elements 2 and 4 are independent, giving two orders: 2 then 4, or 4 then 2.
Number of linear extensions from this branch: 2.
Case: first element is 3
If the second element is 1, then the remaining elements 2 and 4 are independent, giving two orders: 2 then 4, or 4 then 2.
If the second element is 4, then the remaining elements are 1 and 2 with the relation 1 before 2, so the order must be 1 then 2 (only one possibility).
Number of linear extensions from this branch: 2 + 1 = 3.
Total number of linear extensions = 2 (first = 1 branch) + 3 (first = 3 branch) = 5.
Therefore, the number of total orders on {1,2,3,4} that contain the partial order P is 5.
A video solution is available for this question — log in and enroll to watch it.