A partial order ≤ is defined on the set S = {x, b1, b2, … bn, y} as x ≤ bifor all i and bi ≤ y for all i, where n ≥ 1. The number of total orders on the set S which contain the partial order ≤ is ______
A. n+4
B. n2
C. n!
D. 3
Answer:C
A partial order ≤ is defined on the set S = {x, b1, b2, … bn, y} as x ≤ bifor all i and bi ≤ y for all i, where n ≥ 1. The number of total orders on the set S which contain the partial order ≤ is ______
A. n+4 B. n2 C. n! D. 3
Explanation: To make this partial order a total order, we need the relation to hold for every two element of the partial order. Currently, there is no relation between any bi and bj. So, for every bi and bj, we have to add either (bi, bj) or (bj, bi) in total order. So, this translates to giving an ordering for n elements between x and y, which can be done in n! ways.