Let $P$ be the partial order defined on the set $\{1,2,3,4\}$ as follows $$P = \{(x,x) \mid x \in \{1,2,3,4\}\} \cup \{(1,2), (3,2), (3,4)\}$$ The number of total orders on $\{1,2,3,4\}$ that contain $P$ is _________

A total order containing a partial order $P$ is also known as a linear extension of $P$.

The given partial order $P$ imposes the following strict precedence relations between distinct elements:

• $1 < 2$

• $3 < 2$

• $3 < 4$

We need to find the number of permutations $(x_1, x_2, x_3, x_4)$ of the set $\{1, 2, 3, 4\}$ that satisfy these three constraints.

The minimal elements of the poset (elements with no predecessors) are $1$ and $3$.

Case 1: $1$ appears first.

• The permutation begins with $1$: $(1, \_, \_, \_)$.

• The remaining elements to arrange are $\{2, 3, 4\}$.

• Since $3 < 2$ and $3 < 4$, $3$ must precede both $2$ and $4$.

• Thus, $3$ must be in the second position: $(1, 3, \_, \_)$.

• The remaining elements $\{2, 4\}$ have no relative precedence between them, giving $2$ valid permutations:

  1. $1 < 3 < 2 < 4$

  2. $1 < 3 < 4 < 2$

Case 2: $3$ appears first.

• The permutation begins with $3$: $(3, \_, \_, \_)$.

• The remaining elements to arrange are $\{1, 2, 4\}$.

• The only remaining constraint is $1 < 2$, while $4$ can be placed in any position relative to $1$ and $2$.

• The number of ways to arrange $\{1, 2, 4\}$ such that $1 < 2$ is:

  $$\frac{3!}{2!} = 3$$

• The $3$ valid permutations are:

  1. $3 < 4 < 1 < 2$

  2. $3 < 1 < 4 < 2$

  3. $3 < 1 < 2 < 4$

Adding both cases together:

Thus, the number of total orders on $\{1,2,3,4\}$ that contain $P$ is 5.