Question

A partial order ≤ is defined on the set S = {x, b1, b2, … bn, y} as x ≤ bi for 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) n^2

(c) n!

(d) 3

The question was posed to me in an online interview.

Enquiry is from Relations topic in section Relations of Discrete Mathematics

Answer 1

The correct choice is (c) n!

Easy 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.