edited by
8,786 views
42 votes
42 votes

A partial order $≤$ is defined on the set $S=\left \{ x, a_1, a_2, \ldots, a_n, y \right \}$ as $x$ $\leq _{i}$ $a_{i}$ for all $i$ and $a_{i}\leq y$ for all $i$, where $n ≥ 1$. The number of total orders on the set S which contain the partial order $≤$ is

  1. $n!$
  2. $n+2$
  3. $n$
  4. $1$
edited by

2 Answers

Best answer
60 votes
60 votes

To make this partial order a total order, we need the relation to hold for every two element of the partial order. Currently between any $a_i$ and $a_j,$ there is no relation. So, for every $a_i, a_j,$ we have to add either $(a_i, a_j)$ or $(a_j, a_i)$ in total order. So, this translates to giving an ordering for $n$ elements between $x$ and $y,$ which can be done in $n!$ ways. So, answer is (a).

The bottom figure is for a total order. We can permute the $a_i$ from $i = 1$ to $n,$ and each permutation will also be a total order containing the given partial order. 

edited by
9 votes
9 votes

The given POSET is drawn as shown in the best answer here. To make this into a TOSET, we have to make it a chain. So, connect all the a's together, and link one end of the "a chain" with x, and the other end with y.

The whole "a chain" can be made in $n!$ ways, and x and y are fixed.

So, possible Total orders = $n!$

Option A

Answer:

Related questions

54 votes
54 votes
6 answers
1
Kathleen asked Sep 29, 2014
21,136 views
The number of equivalence relations of the set $\{1,2,3,4\}$ is$15$$16$$24$$4$