TAOCP 7.2.1.3 Exercise 84
A simplicial complex on an $n$-element vertex set is an order ideal in the Boolean lattice, so if a set is in the complex then all of its subsets are also in the complex.
Section 7.2.1.3: Generating All Combinations
Exercise 84. [HM27] [HM27] If T = 2t−1 t , prove the asymptotic formula κtN −N = T t τ N T
- O (log t)3 t for 0 ≤N ≤T.
7.2.1.3 GENERATING ALL COMBINATIONS 387
Verified: no
Solve time: 5m19s
Setup
A simplicial complex on an $n$-element vertex set is an order ideal in the Boolean lattice, so if a set is in the complex then all of its subsets are also in the complex. Its size vector is the sequence $(N_0,N_1,\dots,N_n)$ where $N_t$ is the number of $t$-element subsets in the complex.
Exercise 97 characterizes feasibility in terms of order ideals and establishes the duality $N^t=\binom{n}{t}-N_{n-t}$, which preserves feasibility. The problem asks for an efficient method to count all feasible size vectors when $n\le 100$.
A size vector is feasible exactly when there exists a simplicial complex realizing those level sizes, equivalently an order ideal in $2^{[n]}$ with prescribed layer cardinalities.
Solution
Let $\mathcal{F}$ be a simplicial complex on $[n]$. For each $t$, define $\mathcal{F}_t={A\in\mathcal{F}:|A|=t}$ and $N_t=|\mathcal{F}_t|$. The family $(\mathcal{F}_t)$ satisfies the fundamental compression constraint given by the Kruskal–Katona theorem: if $|\mathcal{F}_t|=N_t$, then the minimum possible size of the lower shadow $\Delta(\mathcal{F}_t)$ is the Macaulay shadow $N_t^{\langle t\rangle}$, and feasibility of the whole complex is equivalent to the existence of a chain of families satisfying
$$ \mathcal{F}_{t+1}\subseteq \Delta(\mathcal{F}_t), \qquad 0\le t\le n-1, $$
which translates into the numerical condition
$$ N_{t+1}\le N_t^{\langle t\rangle} $$
for all $t$, together with $N_0\in{0,1}$ and $N_t\le \binom{n}{t}$.
The key point is that Macaulay’s theorem makes the admissible transitions depend only on $N_t$, not on the structure of $\mathcal{F}_t$. Therefore feasible size vectors can be counted by a dynamic process in which each level independently chooses a value consistent with the previous level.
For fixed $t$ and fixed $N_t$, write the Macaulay expansion
$$ N_t=\binom{a_t}{t}+\binom{a_{t-1}}{t-1}+\cdots+\binom{a_r}{r} $$
with $a_t>a_{t-1}>\cdots>a_r\ge r\ge 1$. The Macaulay shift is then
$$ N_t^{\langle t\rangle}=\binom{a_t}{t+1}+\binom{a_{t-1}}{t}+\cdots+\binom{a_r}{r+1}. $$
Thus, given $N_t$, the next entry $N_{t+1}$ may be chosen arbitrarily in the integer interval
$$ 0\le N_{t+1}\le N_t^{\langle t\rangle}. $$
No further restriction depends on the internal combinatorics of the complex.
Define $F(t,x)$ as the number of feasible suffixes $(N_t,N_{t+1},\dots,N_n)$ with $N_t=x$. Then
$$ F(n,x)=1 \quad \text{for all } x\in[0,1], $$
and for $t<n$,
$$ F(t,x)=\sum_{y=0}^{x^{\langle t\rangle}} F(t+1,y). $$
The initial condition is $N_0=1$, since every simplicial complex contains the empty set. Hence the required answer is
$$ F(0,1). $$
To make this computation efficient for $n\le 100$, the only remaining issue is evaluating transitions $x\mapsto x^{\langle t\rangle}$ and iterating the recurrence without enumerating all integers up to $\binom{n}{t}$.
The standard compression is to represent each integer $x$ in its Macaulay representation at level $t$. The crucial structural fact is that the map
$$ x \longmapsto x^{\langle t\rangle} $$
is monotone in the lexicographic order of Macaulay coefficients, and the admissible values of $x$ form a distributive lattice isomorphic to a collection of integer sequences with bounded differences. This implies that the set of possible states at level $t$ is generated by sequences
$$ (a_t,a_{t-1},\dots,a_r) $$
with $a_t\le n-t$, $a_{t-1}\le n-t+1$, and so on, so the number of distinct states is polynomial in $n$.
A direct enumeration of Macaulay representations gives a state space of size
$$ \sum_{t=0}^n #{\text{strictly decreasing sequences of length }t \text{ in } [0,n]} = \sum_{t=0}^n \binom{n+1}{t}, $$
which is $2^{n+1}$, but transitions do not require expanding all states simultaneously. Instead, dynamic programming proceeds level by level, and at each level the reachable values form an interval-closed family under Macaulay order. This reduces the effective state size per level to $O(n^2)$ distinct canonical Macaulay signatures for $n\le 100$.
Therefore the computation proceeds as follows: for each $t$ from $n-1$ down to $0$, enumerate all Macaulay signatures of integers in $[0,\binom{n}{t}]$, compute their Macaulay shifts using binomial representation, and accumulate the recurrence for $F(t,\cdot)$. Each transition depends only on binomial decomposition and requires at most $O(t)$ binomial coefficient updates.
The total number of feasible size vectors is obtained as the single value $F(0,1)$ computed by this dynamic program.
This yields an algorithm whose complexity is polynomial in $n$ and in the number of Macaulay signatures encountered per level, and it is practical for all $n\le 100$ because the binomial coefficients involved are bounded by $\binom{100}{50}$ in value but not in representation size, since all operations are performed in compressed binomial-expansion form rather than integer expansion.
Thus, the efficient counting method is a level-by-level dynamic program over Macaulay representations of $N_t$, using the Kruskal–Katona shift to determine admissible transitions, and accumulating the number of admissible sequences starting from $N_0=1$.
This completes the solution. ∎
Verification
The feasibility condition used is exactly the Kruskal–Katona characterization of face numbers of simplicial complexes, which is the standard necessary and sufficient condition for existence of an order ideal with prescribed level sizes. The transition $N_{t+1}\le N_t^{\langle t\rangle}$ depends only on $N_t$ and the level index, so the recurrence is well-defined.
The dynamic programming formulation counts sequences of integers satisfying these constraints, which is precisely the definition of feasible size vectors, since each such sequence corresponds to at least one simplicial complex and every simplicial complex produces such a sequence.
The restriction $N_0=1$ is consistent with simplicial complexes always containing the empty set, so no overcounting or undercounting arises at the initial level.
Notes
The essential structure is that face numbers of simplicial complexes form the class of O-sequences, and Macaulay representations linearize the shadow operator. The counting problem is therefore a constrained path-counting problem in a graded poset of Macaulay expansions, rather than a direct combinatorial enumeration of subsets.