TAOCP 7.1.4 Exercise 260
Let $a_1 \dots a_n$ be a restricted growth string with a_1 = 0,\qquad a_{j+1} \le 1 + \max(a_1,\dots,a_j)\quad (1 \le j < n).
Section 7.1.4: Binary Decision Diagrams
Exercise 260. ▶ [M27] [M27] We will see in Section 7.2.1.5 that every partition of {1, . . . , n} into disjoint subsets corresponds to a “restricted growth string” a1 . . . an, which is a sequence of nonnegative integers with a1 = 0 and aj+1 ≤1 + max(a1, . . . , aj) for 1 ≤j < n. Elements j and k belong to the same subset of the partition if and only if aj = ak. a) Let xj,k = [aj = k] for 0 ≤k < j ≤n, and let Rn be the function of these n+1 2 variables that is true if and only if a1 . . . an is a restricted growth string. (By studying this Boolean function we can study the family of all set partitions, and by placing further restrictions on Rn we can study set partitions with special properties. There are ϖ100 ≈5 × 10115 set partitions when n = 100.) Calculate B(R100) and Z(R100). Approximately how large are B(Rn) and Z(Rn) as n → ∞? b) Show that, with a proper ordering of the variables xj,k, the BDD base for {R1, . . . , Rn} has the same number of nodes as the BDD for Rn alone. c) We can also use fewer variables, approximately n lg n instead of n+1 2 , if we represent each ak as a binary integer with ⌈lg k⌉bits. How large are the BDD and ZDD bases in this representation of set partitions?
Verified: no
Solve time: 1m12s
Setup
Let $a_1 \dots a_n$ be a restricted growth string with
$$ a_1 = 0,\qquad a_{j+1} \le 1 + \max(a_1,\dots,a_j)\quad (1 \le j < n). $$
For $0 \le k < j \le n$, define Boolean variables
$$ x_{j,k} = [a_j = k]. $$
The function $R_n$ is defined on all these variables and is true exactly when the variables encode a valid restricted growth string.
A valid assignment to the variables corresponds to an integer sequence $a_1,\dots,a_n$ satisfying:
for each $j$, exactly one $x_{j,k}$ is true for $0 \le k < j$, and the growth constraint holds.
Let $B(R_n)$ and $Z(R_n)$ denote the sizes of the reduced ordered BDD and ZDD for $R_n$ under a variable ordering consistent with increasing $j$.
The goal is to determine $B(R_{100})$, $Z(R_{100})$, and asymptotic forms of $B(R_n)$, $Z(R_n)$, and to compare bases under alternative encodings.
Solution
The structure of $R_n$ is governed entirely by prefixes of restricted growth strings. Fix $j$ with $1 \le j \le n$, and consider the subfunction obtained by assigning values to all variables $x_{t,k}$ with $t \le j$. Such an assignment determines a partial sequence $a_1,\dots,a_j$ provided the “exactly one per row” constraints are satisfied.
Two assignments to the first $j$ layers of variables induce the same continuation behavior on the remaining variables if and only if they define the same partition of ${1,\dots,j}$, because in a restricted growth string each value $a_t$ identifies the block of element $t$, and the constraint $a_{t+1} \le 1 + \max(a_1,\dots,a_t)$ ensures that relabelings are canonical. Hence the induced subfunction depends only on the partition of the first $j$ elements.
Every partition of ${1,\dots,j}$ arises from exactly one restricted growth prefix, so the number of distinct subfunctions after processing level $j$ is exactly the Bell number $B_j$.
Now fix a variable ordering that respects layers $j = 1,2,\dots,n$, with all variables $x_{j,k}$ for fixed $j$ placed consecutively and with all variables for smaller $j$ preceding those for larger $j$. In such an ordered BDD, every node reached after processing variables up to level $j$ corresponds to a distinct subfunction of the remaining variables, and reduction merges identical subfunctions. Thus the number of nodes at level $j$ equals the number of distinct subfunctions determined by prefixes of length $j$, which is $B_j$.
Each node at level $j$ has outgoing edges to nodes at level $j+1$, and sinks correspond to $j=n$. Therefore the total number of nodes in the BDD is
$$ B(R_n) = \sum_{j=0}^n B_j + O(1), $$
where the additive constant accounts for the sink nodes.
The asymptotic growth of Bell numbers satisfies $B_n \gg \sum_{j < n} B_j$, since $B_n / B_{n-1} \to \infty$. Therefore
$$ B(R_n) = \Theta(B_n). $$
For $n = 100$, this yields
$$ B(R_{100}) = \Theta(B_{100}). $$
Using the standard asymptotic estimate $B_{100} \approx 4.75 \times 10^{115}$, the BDD size is on the order of $10^{115}$.
For ZDDs, the same layered decomposition applies. The zero-suppressed reduction only removes nodes whose HI-edges lead to the 0-sink when all variables are absent, but in this construction each choice of $a_j$ corresponds to a required selection of exactly one $k$, so every level still contains one representative per partition of ${1,\dots,j}$. No additional compression beyond identification of identical subfunctions occurs, hence
$$ Z(R_n) = \Theta(B_n), $$
and in particular
$$ Z(R_{100}) = \Theta(B_{100}). $$
(b) Base equivalence
With a proper ordering that interleaves variables by increasing $j$ and places all $x_{j,k}$ in a contiguous block, the BDD base constructed for the family ${R_1,\dots,R_n}$ produces nodes that correspond exactly to subfunctions determined by prefixes of restricted growth strings.
The subfunction induced after processing variables up to level $j$ depends only on the partition of ${1,\dots,j}$, and this dependency is independent of whether the remaining variables belong to $R_j$ alone or to the larger family ${R_1,\dots,R_n}$. Therefore every node created in the shared base appears already in the BDD for $R_n$, and no additional distinct subfunctions arise in the family construction.
Hence the base has exactly the same node set as the single-function BDD for $R_n$, and the sizes coincide.
(c) Binary encoding of $a_k$
Replace the indicator variables $x_{j,k}$ by binary encodings of each $a_j$, using $\lceil \log j \rceil$ bits per position. The total number of variables becomes
$$ N = \sum_{j=1}^n \lceil \log j \rceil = \Theta(n \log n). $$
The function remains the characteristic function of restricted growth strings, so each prefix of length $j$ still induces exactly one partition of ${1,\dots,j}$. The subfunction after processing the first $j$ encoded integers depends only on that partition, not on the bit representation.
Thus the number of distinct subfunctions at level $j$ is still $B_j$, independent of encoding. The BDD node count is therefore unchanged up to constant factors:
$$ B(R_n) = \Theta!\left(\sum_{j=0}^n B_j\right) = \Theta(B_n). $$
The same argument applies to ZDDs, since zero-suppression does not merge subfunctions corresponding to distinct partitions.
Hence both the BDD base and the ZDD base under binary encoding satisfy
$$ B(R_n) = \Theta(B_n),\qquad Z(R_n) = \Theta(B_n). $$
Verification
The critical invariant is that every node at level $j$ corresponds to a distinct partition of ${1,\dots,j}$. Distinct partitions induce distinct continuation constraints on $a_{j+1},\dots,a_n$, since admissible values depend on the current maximum block index and the equality structure of previous elements. This prevents two different partitions from yielding identical subfunctions.
Every partition of size $j$ is realizable by a restricted growth prefix, since assigning each element its first-occurrence index constructs a canonical representative. Hence the mapping from nodes to partitions is both injective and surjective, giving exactly $B_j$ nodes per level.
Summing over all levels yields total size $\sum_{j=0}^n B_j$, and monotonic dominance of $B_n$ over earlier terms implies asymptotic equivalence.
This completes the solution. ∎