Exercise 16. [M08] In how many ways can the partial ordering represented by (39) be sorted topologically?

Verified: yes
Solve time: 36m57s

The partial ordering (39) is defined on the pairs ((q_i, p_i)) of the two-line array [ \begin{pmatrix} q_1 & q_2 & \cdots & q_n \ p_1 & p_2 & \cdots & p_n \end{pmatrix}

\begin{pmatrix} 1 & 3 & 5 & 6 & 8 \ 7 & 2 & 9 & 5 & 3 \end{pmatrix} ] with the order ((q_i, p_i) < (q_j, p_j)) if and only if (i < j) and (p_i < p_j).

Label the five elements: [ A = (1,7),\quad B = (3,2),\quad C = (5,9),\quad D = (6,5),\quad E = (8,3). ] The relations are determined by checking all pairs (i < j):

(i=1): (p_1=7). (7 < 9) ((j=3)) gives (A < C). No other (p_j > 7).
(i=2): (p_2=2). (2 < 9) ((j=3)) gives (B < C); (2 < 5) ((j=4)) gives (B < D); (2 < 3) ((j=5)) gives (B < E).
(i=3): (p_3=9). No (p_j > 9).
(i=4): (p_4=5). No (p_j > 5) with (j>4). Thus the Hasse diagram has minimal elements (A, B); maximal elements (C, D, E); and edges (A \to C), (B \to C), (B \to D), (B \to E). No other comparabilities exist.

A topological sort (linear extension) is a total order consistent with these relations.
Observe that (B) must precede (C, D, E). The only element that can appear before (B) is (A) (since (A) is incomparable with (B), and (C, D, E) are all greater than (B)). Hence (B) is either first or second.

Case 1: (B) is first.
The remaining elements ({A, C, D, E}) have the single constraint (A < C).
The number of linear extensions of this 4-element poset is (\frac{4!}{2} = 12).
Case 2: (B) is second.
The first element must be (A). The remaining three elements ({C, D, E}) are mutually incomparable, so they can appear in any of (3! = 6) orders.

(B) cannot be third or later because at most one element ((A)) can precede it.
Total topological sorts: (12 + 6 = 18).

Verification by recurrence on the poset (P):

Remove (A): (P \setminus {A}) has elements (B, C, D, E) with (B < C, D, E). Linear extensions: (B) first, then (C, D, E) in any order (\Rightarrow 3! = 6).
Remove (B): (P \setminus {B}) has elements (A, C, D, E) with (A < C). Linear extensions: (\frac{4!}{2} = 12). Since (A) and (B) are the only minimal elements, (L(P) = L(P \setminus {A}) + L(P \setminus {B}) = 6 + 12 = 18), confirming the count.

[ \boxed{18} ]

TAOCP 5.1.4 Exercise 16

The partial ordering (39) is defined on the pairs ((q_i, p_i)) of the two-line array [ \begin{pmatrix} q_1 & q_2 & \cdots & q_n \ p_1 & p_2 & \cdots & p_n \end{pmatrix}