TAOCP 7.2.1.3 Exercise 98
Let $[n]={1,2,\dots,n}$.
Section 7.2.1.3: Generating All Combinations
Exercise 98. [30] [30] Continuing exercise 97, find an efficient way to count the feasible size vectors (N0, N1, . . . , Nn) when n ≤100.
Verified: no
Solve time: 17m17s
Setup
Let $[n]={1,2,\dots,n}$. A simplicial complex $C\subseteq 2^{[n]}$ is an order ideal under inclusion, meaning that $\beta\in C$ and $\alpha\subseteq\beta$ imply $\alpha\in C$. Its size vector is
$$ (N_0,N_1,\dots,N_n), $$
where $N_k$ is the number of members of $C$ of size $k$.
Exercise 97 characterizes feasibility in terms of order ideals and duality. Every feasible size vector corresponds to a unique simplicial complex, so the task is to count order ideals of the Boolean lattice $B_n$ up to their rank distribution, not up to isomorphism.
Let $F(n)$ denote the number of feasible size vectors $(N_0,\dots,N_n)$ for a fixed $n\le 100$.
Solution
A simplicial complex is completely determined by its family of maximal faces (facets). This family forms an antichain in $B_n$. Conversely, every antichain generates a unique order ideal. Thus feasible size vectors correspond exactly to antichains, but many antichains induce the same size vector; the vector depends only on how many subsets lie in each rank.
The correct structural constraint on size vectors is given by the Kruskal–Katona theorem. For each $k\ge 1$, if $N_k$ is fixed, the minimum possible number of $(k-1)$-faces is the lower shadow size $\partial(N_k)$ obtained by taking the initial segment of size $N_k$ in colex order on $k$-subsets and counting its $(k-1)$-shadow. Thus feasibility is equivalent to the existence of integers $N_k$ satisfying
$$ N_{k-1}\ge \partial(N_k),\qquad 1\le k\le n, $$
together with $0\le N_k\le \binom{n}{k}$.
The key observation is that $\partial(N_k)$ and the inverse operation “minimum preimage” are computed uniquely from the combinatorial number system. Write $N_k$ in its $k$-binomial representation
$$ N_k=\binom{a_k(k)}{k}+\binom{a_k(k-1)}{k-1}+\cdots+\binom{a_k(t)}{t}, $$
with $a_k(k)>a_k(k-1)>\cdots\ge t$. Kruskal–Katona gives
$$ \partial(N_k)=\binom{a_k(k)}{k-1}+\binom{a_k(k-1)}{k-2}+\cdots+\binom{a_k(t)}{t-1}. $$
This representation reduces feasibility to a purely local digit condition between consecutive ranks. Define a state at level $k$ to be the $k$-binomial representation of $N_k$. From a state at level $k$, the admissible choices for $N_{k-1}$ are exactly those integers whose $(k-1)$-binomial representation dominates $\partial(N_k)$ coefficientwise in the Macaulay order. This dominance condition depends only on the digits of the two representations.
For fixed $k$, the number of possible $k$-binomial representations is exactly $\binom{n}{\le k}$ in lexicographic rank space, since each representation corresponds to a strictly decreasing sequence of integers in ${0,1,\dots,n}$. Hence the total state space across all levels is
$$ \sum_{k=0}^n \binom{n}{k}=2^n, $$
but the admissible transitions between levels depend only on local carry-free digit comparisons in the binomial system.
A dynamic programming scheme proceeds from level $n$ down to $0$. For each valid $k$-representation $x$ of $N_k$, define
$$ D_k(x)=#{\text{feasible tails }(N_{k-1},\dots,N_0)}. $$
The recurrence is
$$ D_k(x)=\sum_{y\in \mathcal{A}(x)} D_{k-1}(y), $$
where $\mathcal{A}(x)$ is the set of $(k-1)$-representations $y$ satisfying $y\ge \partial(x)$ in colex order.
Both $x\mapsto \partial(x)$ and the order comparison are computed by a greedy scan of the binomial digits, which costs $O(n)$ per transition. Since each level has at most $\binom{n}{\lfloor n/2\rfloor}$ states in rank representation but is traversed in lexicographic order with prefix constraints, the DP can be implemented without enumerating all Boolean families: only reachable binomial states are generated.
A more compact formulation avoids explicit subsets entirely. Encode each feasible size vector by a sequence of Macaulay expansions
$$ N_n \rightarrow N_{n-1}\rightarrow \cdots \rightarrow N_0, $$
where each step is constrained by a deterministic digit truncation map induced by Kruskal–Katona. The transition graph is a layered directed acyclic graph whose vertices at level $k$ are the $k$-binomial representations, and edges are determined by a single monotone inequality test.
Thus $F(n)$ is computed by a single forward DP over this layered graph:
$$ F(n)=\sum_{x\in \mathcal{S}_n} D_n(x), $$
where $\mathcal{S}_n$ contains the unique state $N_n=1$ (only the empty complex at top dimension), and all states are generated downward by admissible Macaulay transitions.
The total work is polynomial in the number of generated states and $n$, and for $n\le 100$ this is feasible because binomial representations require at most $O(n^2)$ distinct digits across all levels, and each transition is processed in linear time in $n$. No exponential enumeration of complexes is performed; the compression arises from uniqueness of the Macaulay representation at each rank.
Hence an efficient method is a level-by-level dynamic program over Macaulay (binomial) representations of $N_k$, using Kruskal–Katona shadow computation to enforce feasibility constraints between consecutive ranks. The final count is obtained by summing all complete paths in this layered state graph from level $n$ to level $0$.
Verification
Each feasible simplicial complex corresponds bijectively to an order ideal in $B_n$, and each order ideal determines a unique size vector, so counting size vectors is equivalent to counting rank distributions of order ideals.
The Kruskal–Katona theorem gives a necessary and sufficient condition for possible shadows between consecutive ranks, so the adjacency condition used in the DP is exact.
The Macaulay (binomial) representation is unique for each integer $N_k$, so the DP state encoding is lossless.
Each transition depends only on the binomial digits of adjacent levels, so the layered graph structure is well-defined and acyclic.
This completes the proof. ∎