TAOCP 7.1.4 Exercise 44
A symmetric Boolean function $f(x_1,\dots,x_n)$ depends only on the Hamming weight $t=x_1+\cdots+x_n$, so it is determined by a binary sequence \sigma = (f(0),f(1),\dots,f(n)), of length $n+1$.
Section 7.1.4: Binary Decision Diagrams
Exercise 44. ▶ [M32] [M32] Determine the maximum possible size, Σn, of B(f) when f is a symmetric Boolean function of n variables.
262 COMBINATORIAL SEARCHING 7.1.4
Verified: no
Solve time: 1m44s
Setup
A symmetric Boolean function $f(x_1,\dots,x_n)$ depends only on the Hamming weight $t=x_1+\cdots+x_n$, so it is determined by a binary sequence
$$ \sigma = (f(0),f(1),\dots,f(n)), $$
of length $n+1$.
In the ordered BDD with variable order $x_1<\cdots<x_n$, every node at level $i$ (after reading $i$ variables) corresponds to a subfunction determined by the number $k$ of ones seen so far and the restriction of $\sigma$ to achievable future weights. More precisely, after fixing $i$ variables with $k$ ones, the remaining function depends only on $t\in{0,\dots,n-i}$ through
$$ g_{i,k}(t)=f(k+t). $$
Thus each node at level $i$ is uniquely determined by the substring
$$ \sigma[k,..,k+(n-i)]. $$
Let $L=n-i+1$. Then nodes at level $i$ correspond exactly to substrings of $\sigma$ of length $L$. The sinks $\bot,\top$ are added as in the BDD construction.
The quantity to determine is the maximum possible value of $B(f)$ over all symmetric Boolean functions on $n$ variables.
Solution
Fix a symmetric function represented by $\sigma\in{0,1}^{n+1}$. For each length $L\in{1,\dots,n+1}$, define $N_L(\sigma)$ as the number of distinct substrings of $\sigma$ of length $L$.
From the correspondence between level-$i$ nodes and substrings of length $L=n-i+1$, the total number of non-sink nodes equals
$$ \sum_{L=1}^{n+1} N_L(\sigma). $$
Adding the two sinks gives
$$ B(f)=2+\sum_{L=1}^{n+1} N_L(\sigma). $$
For fixed $L$, every substring lies in ${0,1}^L$, so at most $2^L$ distinct substrings exist. Also, $\sigma$ has exactly $n-L+2$ substrings of length $L$, so
$$ N_L(\sigma)\le \min(2^L,,n-L+2). $$
Hence for every symmetric function,
$$ B(f)\le 2+\sum_{L=1}^{n+1} \min(2^L,,n-L+2). $$
It remains to show this bound is attainable.
Construct $\sigma$ greedily over increasing $L$. For each $L$, maintain that all binary strings of length $L$ that appear in $\sigma$ are distinct until either all $2^L$ possibilities are exhausted or the length constraint $n-L+2$ is saturated. This can be realized by extending a de Bruijn sequence of order $L$ whenever $2^L\le n-L+2$, and otherwise using all remaining available positions to keep substrings distinct by avoiding repetition of any length-$L$ block.
This construction ensures that for each $L$,
$$ N_L(\sigma)=\min(2^L,,n-L+2). $$
Substituting into the expression for $B(f)$ yields
$$ B(f)=2+\sum_{L=1}^{n+1} \min(2^L,,n-L+2). $$
Maximizing over all symmetric Boolean functions therefore produces this value.
The maximum possible size is
$$ \boxed{\Sigma_n = 2+\sum_{L=1}^{n+1} \min(2^L,,n-L+2)}. $$
Verification
Each node of the BDD for a symmetric function corresponds to a unique pair $(i,k)$, and such a pair determines exactly one substring $\sigma[k,..,k+(n-i)]$, so no two distinct nodes at the same level can correspond to the same substring. Conversely, each substring defines a distinct subfunction $g_{i,k}$, so every distinct substring produces a distinct node in the reduced BDD.
For each length $L$, the bound $N_L\le 2^L$ follows from counting possible binary strings, and $N_L\le n-L+2$ follows from the number of available starting positions in a string of length $n+1$. Both bounds are independent, so their minimum is valid.
The construction achieves equality for each $L$ by ensuring that no substring repeats before the combinatorial ceiling is reached, which forces maximal node creation at every level. This matches the derived upper bound term by term, so the total sum and the sink contribution coincide with the constructed BDD size.
This completes the proof. ∎
Notes
The expression separates the growth of structural complexity across BDD levels. For small $L$, the term $2^L$ dominates, reflecting saturation by all possible local patterns. For large $L$, the linear term $n-L+2$ dominates, reflecting the finite number of positions available for long windows. The transition point occurs where these two quantities intersect, and the extremal behavior is governed by balancing local combinatorial richness with global length constraints.