A partial order

Question

A partial order <= is defined on the set S = {a_0, a_1, ..., a_n} as a_i <= a_i for all i and a_i <= a_{i+1} for all i, where n >= 1. The number of total orders on the set S which contain the partial order <= is

A. 1
B. n
C. (n+1)!/2
D. (n+1)!

Accepted Answer

A. 1 The given partial order says a_0 <= a_1 <= ... <= a_n. By transitivity, a_i <= a_j for all i <= j, so every pair of elements is already comparable. This means the partial order is already a total order (a chain). A total order extending a partial order must preserve all existing relations. Since all elements are fixed in the order a_0, a_1, ..., a_n, exactly 1 total order extends it.

A partial order <= is defined on the set S = {a_0, a_1, ..., a_n} as a_i <= a_i for all i and a_i <= a_{i+1} for all i, where n >= 1. The number of total orders on the set S which contain the partial order <= is A. 1 B. n C. (n+1)!/2 D. (n+1)!