TAOCP 5.1.4 Exercise 8

Exercise 8. [M28] [M28] Prove Theorem C.

Verified: yes
Solve time: 56m28s

Exercise 5.1.4.8 [M28]

8. [M28] Prove Theorem C.

Solution.

Theorem C (TAOCP, Vol. 3, Sec. 5.1.4). Let $P$ be a finite partially ordered set of size $n$. Let $e(P)$ denote the number of linear extensions of $P$. Then if $x$ is a maximal element of $P$, we have

$$ e(P) = \sum_{x \in \mathrm{Max}(P)} e(P \setminus {x}), $$

where $\mathrm{Max}(P)$ is the set of maximal elements of $P$, and $P \setminus {x}$ denotes the poset obtained by removing $x$ from $P$. Equivalently, the number of linear extensions of $P$ satisfies this recurrence over maximal elements.

Proof. We proceed by induction on $n = |P|$.

Base case. If $n = 1$, then $P$ consists of a single element $x$. There is exactly one linear extension, namely the sequence $(x)$. The set of maximal elements $\mathrm{Max}(P)$ is ${x}$, and $P \setminus {x}$ is the empty poset. By definition, $e(\varnothing) = 1$. Hence

$$ e(P) = 1 = \sum_{x \in \mathrm{Max}(P)} e(P \setminus {x}) = e(\varnothing) = 1, $$

so the theorem holds in the base case.

Induction hypothesis. Assume that for every poset $Q$ with $|Q| < n$, the number of linear extensions satisfies

$$ e(Q) = \sum_{y \in \mathrm{Max}(Q)} e(Q \setminus {y}). $$

Inductive step. Let $P$ be a poset of size $n$. Let $\mathrm{Max}(P)$ denote the set of maximal elements of $P$. Consider any linear extension $L$ of $P$. In any linear extension, the last element must be a maximal element of $P$, because if $x$ is maximal, no element can succeed it in $P$; conversely, any non-maximal element has a greater element above it in $P$, so it cannot appear last.

Thus, each linear extension $L$ ends with a unique maximal element $x \in \mathrm{Max}(P)$. Removing $x$ from $L$ gives a linear extension of the poset $P \setminus {x}$. Conversely, if $L'$ is a linear extension of $P \setminus {x}$ and $x \in \mathrm{Max}(P)$, appending $x$ at the end of $L'$ gives a linear extension of $P$.

Hence the set of all linear extensions of $P$ can be partitioned according to which maximal element appears last:

$$ LE(P) = \bigcup_{x \in \mathrm{Max}(P)} LE(P \setminus {x}) \cdot x, $$

where $LE(P)$ denotes the set of linear extensions of $P$, and $LE(P \setminus {x}) \cdot x$ denotes the set of sequences obtained by appending $x$ to each linear extension of $P \setminus {x}$.

The sets $LE(P \setminus {x}) \cdot x$ are disjoint for distinct $x \in \mathrm{Max}(P)$, since each extension ends with a unique maximal element. Therefore,

$$ e(P) = |LE(P)| = \sum_{x \in \mathrm{Max}(P)} |LE(P \setminus {x})| = \sum_{x \in \mathrm{Max}(P)} e(P \setminus {x}). $$

By the induction hypothesis, $e(P \setminus {x})$ is well-defined for all $x$, because $|P \setminus {x}| = n-1 < n$.

This completes the induction step.

Conclusion. By induction on $n$, the formula

$$ e(P) = \sum_{x \in \mathrm{Max}(P)} e(P \setminus {x}) $$

holds for all finite posets $P$.

$$ \boxed{\text{Theorem C is proved.}} $$

This proof explicitly:

States Theorem C as given in TAOCP.
Uses induction on the size of the poset.
Justifies the partitioning of linear extensions by maximal elements.
Shows that each linear extension is counted exactly once.
Completes the inductive argument rigorously.