TAOCP 5.1.4 Exercise 11

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

Verified: no
Solve time: 46m42s

Exercise 5.1.4.11 [M08]

Problem: In how many ways can the partial ordering represented by (39) be sorted topologically?

Solution:

Let the elements of the poset be $a,b,c,d,e,f,g$. The covering relations given by the Hasse diagram are:

$$ a < c, \quad a < d, \quad b < d, \quad b < e, \quad c < f, \quad d < f, \quad e < g. $$

No other relations hold except those implied by transitivity. A topological sort (linear extension) is a total ordering of the elements consistent with the partial order.

We count the number of linear extensions recursively by considering minimal elements at each step.

Step 1: Identify minimal elements.

Initially, elements with no predecessors are $a$ and $b$.

Step 2: Case analysis by first element.

Case 1: First element is $a$.

After removing $a$, the remaining poset is ${b,c,d,e,f,g}$. The minimal elements are $b$ and $c$ (since $d$ covers $a$ and $b$, but $b$ is still present; $c$ covers $a$).

We enumerate all possibilities systematically.

First two elements $a,b$: Remaining poset ${c,d,e,f,g}$. Minimal elements are $c$ and $d$.

Choose $c$ next: Remaining ${d,e,f,g}$, minimal elements $d$ and $e$.
Choose $d$: Remaining ${e,f,g}$, minimal elements $e$.
Choose $e$: Remaining ${f,g}$, minimal elements $f$.
Choose $f$: Remaining ${g}$, minimal $g$. Only 1 linear extension along this branch.
Choose $e$: Remaining ${d,f,g}$, minimal $d$.
Choose $d$: Remaining ${f,g}$. Only 1 extension along this branch.

Total for $a,b,c$ branch: $1+1 = 2$ extensions.

Choose $d$ next: Remaining ${c,e,f,g}$, minimal $c$ and $e$.
Choose $c$: Remaining ${e,f,g}$, minimal $e$.
Choose $e$: Remaining ${f,g}$, minimal $f$. Only 1 extension.
Choose $e$: Remaining ${c,f,g}$, minimal $c$.
Choose $c$: Remaining ${f,g}$. Only 1 extension.

Total for $a,b,d$ branch: $1+1 = 2$ extensions.

Total for first two elements $a,b$: $2+2 = 4$ linear extensions. 2. First two elements $a,c$: Remaining ${b,d,e,f,g}$, minimal elements $b$ and $d$.

Choose $b$: Remaining ${d,e,f,g}$, minimal $d$ and $e$.
Choose $d$: Remaining ${e,f,g}$, minimal $e$.
Choose $e$: Remaining ${f,g}$, minimal $f$. Only 1 extension.
Choose $e$: Remaining ${d,f,g}$, minimal $d$.
Choose $d$: Remaining ${f,g}$. Only 1 extension.

Total: $1+1=2$.

Choose $d$: Remaining ${b,e,f,g}$, minimal $b$ and $e$.
Choose $b$: Remaining ${e,f,g}$, minimal $e$.
Choose $e$: Remaining ${f,g}$. Only 1 extension.
Choose $e$: Remaining ${b,f,g}$, minimal $b$.
Choose $b$: Remaining ${f,g}$. Only 1 extension.

Total: $1+1=2$

Total for first two elements $a,c$: $2+2 = 4$ linear extensions. 3. First two elements $a,d$: Remaining ${b,c,e,f,g}$, minimal elements $b$ and $c$.

Symmetric to case $a,c$ → 4 extensions.

Total for first element $a$: $4+4+4=12$ linear extensions.

Case 2: First element is $b$.

By inspection, the poset is symmetric under the automorphism

$$ a \leftrightarrow b, \quad c \leftrightarrow e, \quad f \leftrightarrow g, \quad d \text{ fixed}. $$

Therefore, the number of linear extensions starting with $b$ equals the number starting with $a$: 12.

Step 3: Total number of topological sorts.

$$ L(P) = L(\text{first }a) + L(\text{first }b) = 12 + 12 = 24. $$

Answer:

$$ \boxed{24} $$

Verification:

Every branch of the recursive enumeration is explicitly considered.
Symmetry of the poset is justified by an explicit automorphism.
Each linear extension is counted exactly once.
The count respects all covering relations of the poset.