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 __________
Answer
5
Explanation
A total order that contains \(P\) is a linear extension of \(P\): an arrangement of 1, 2, 3, 4 in which 1 comes before 2, 3 comes before 2, and 3 comes before 4. Only the minimal elements 1 and 3 can come first.
- First 1: among 2, 3, 4 the element 3 must lead, and 2 and 4 follow in either order: 1, 3, 2, 4 and 1, 3, 4, 2.
- First 3: the remaining 1, 2, 4 only need 1 before 2, which half of their \(3! = 6\) orders satisfy: 3, 1, 2, 4; 3, 1, 4, 2; 3, 4, 1, 2.
So \(2 + 3 = 5\) total orders contain \(P\).
Answer: 5