Relations, partial orders and lattices: GATE CS question with solution

Method. A total order containing $P$ is a way of listing the five elements in a line, smallest first, so that whenever $x\ne y$ and $x⪯y$ in $P$, $x$ appears before $y$ (a linear extension). Read off the structure first:

• $1⪯2$, $1⪯3$, $2⪯4$, $3⪯4$: a diamond with $1$ at the bottom and $4$ at the top.
• $5⪯4$, and $5$ is incomparable with $1,2,3$.

Every other element is below $4$, so $4$ must come last. Among $\{1,2,3\}$, $1$ must come first and $2,3$ can be in either order: $2$ ways ($1,2,3$ or $1,3,2$). Element $5$ only has to precede $4$, so it can be inserted in any of the $4$ gaps of a 3-element line before $4$ (before $1$, between the first two, between the last two, or right before $4$): $4$ ways.

Total $=2\times 4=8$.

The trap. Two slips are common: ignoring $5$ (answer $2$, the diamond alone) or forgetting it is still bounded by $4$ and letting it go anywhere among 5 positions (answer $10$). Another is to count $5!=120$ minus "bad" orders, which is error-prone; placing the forced elements first is faster.

What was tested. Reading a partial order from its pair list, recognising maximal and minimal elements, and counting linear extensions by fixing forced positions and multiplying independent choices.