TAOCP 5.3.4 Exercise 31
A canonical form as described in exercise 30 is a disjunction \[ \tau_1 \lor \tau_2 \lor \cdots \lor \tau_k \qquad (k \ge 1) \] where each \(\tau_i = \bigwedge \{x_j \mid j \in S_i\}\) for some subset...
Section 5.3.4: Networks for Sorting
Exercise 31. [M24] (R. Dedekind, 1897.) Let $\delta_n$ be the number of distinct canonical forms on $x_1, \ldots, x_n$ in the sense of exercise 30. Thus $\delta_1 = 1$, $\delta_2 = 4$, and $\delta_3 = 18$. What is $\delta_4$?
Verified: no
Solve time: 1m15s
Solution
A canonical form as described in exercise 30 is a disjunction
[
\tau_1 \lor \tau_2 \lor \cdots \lor \tau_k \qquad (k \ge 1)
]
where each (\tau_i = \bigwedge {x_j \mid j \in S_i}) for some subset (S_i \subseteq {1,2,\dots,n}), and the family ({S_1,\dots,S_k}) is an antichain (no (S_i) is properly contained in another). The reduction rules of exercise 30 never produce an empty conjunction (the constant 1) or an empty disjunction (the constant 0); therefore every (S_i) is nonempty and (k \ge 1). Hence (\delta_n) equals the number of nonempty antichains of nonempty subsets of an (n)-element set.
A monotone Boolean function of (n) variables is uniquely determined by the antichain of its minimal true sets; the constants 0 and 1 correspond respectively to the empty antichain and the antichain ({\emptyset}). The total number of monotone Boolean functions is the Dedekind number (D(n)). Consequently the number of nonempty antichains of nonempty subsets is (D(n)-2) (subtracting the two constant functions).
The Dedekind numbers for small (n) are [ D(1)=3,\quad D(2)=6,\quad D(3)=20,\quad D(4)=168. ] The given values (\delta_1=1), (\delta_2=4), (\delta_3=18) satisfy (\delta_n = D(n)-2) for (n=1,2,3). Therefore [ \delta_4 = D(4)-2 = 168-2 = 166. ]
\boxed{166}