A partial order ≤ is defined on S = {x, a₁, a₂, ..., aₙ, y} by: x < aᵢ for…
1997
A partial order ≤ is defined on S = {x, a₁, a₂, ..., aₙ, y} by:
x < aᵢ for every i, and
aᵢ ≤ y for every i, where n ≥ 1.
How many total orders (linear extensions) on S extend this partial order?
- A.
n!
- B.
n + 2
- C.
n
- D.
1
Attempted by 21 students.
Show answer & explanation
Correct answer: A
The partial order gives two kinds of constraints:
1. x < aᵢ for every i, so x must come before every middle element.
2. aᵢ ≤ y for every i, so every middle element must come before y.
Therefore, in any total order extending this partial order, x is forced to be first and y is forced to be last.
There is no ordering constraint among a₁, a₂, ..., aₙ themselves. These n middle elements may appear in any order between x and y.
Number of possible arrangements of the middle elements = n!
Hence, the number of total orders extending the partial order is n!.