TAOCP 7.1.4 Exercise 43
Let $f$ be a Boolean function on $2n$ variables and recall that $B(f)$ is the number of beads of $f$, equivalently the number of nodes in its reduced ordered BDD, including sinks.
Section 7.1.4: Binary Decision Diagrams
Exercise 43. ▶ [22] [22] What is B(f) when (a) f(x1, . . . , x2n) = [x1 + · · · + xn = xn+1 + · · · + x2n]? (b) f(x1, . . . , x2n) = [x1 + x3 + · · · + x2n−1 = x2 + x4 + · · · + x2n]?
Verified: no
Solve time: 3m19s
Solution
Let $f$ be a Boolean function on $2n$ variables and recall that $B(f)$ is the number of beads of $f$, equivalently the number of nodes in its reduced ordered BDD, including sinks.
A subfunction of $f$ obtained after fixing a prefix $x_1,\dots,x_k$ depends only on the remaining variables and on whatever scalar parameters summarize all information from the prefix that is relevant to the constraint defining $f$. Distinct nodes in the BDD correspond exactly to distinct such residual functions.
(a) $f(x_1,\dots,x_{2n}) = [x_1 + \cdots + x_n = x_{n+1} + \cdots + x_{2n}]$
Let $S_1 = x_1 + \cdots + x_n$ and $S_2 = x_{n+1} + \cdots + x_{2n}$. The function is $[S_1 = S_2]$.
After reading the first $j$ variables, where $0 \le j \le n$, the only relevant information from the prefix is the integer
$$ i = x_1 + \cdots + x_j. $$
The residual condition becomes
$$ i + (x_{j+1} + \cdots + x_n) = S_2, $$
so the remaining problem depends only on the pair $(j,i)$. For fixed $j$, the value $i$ ranges over $0 \le i \le j$, and different values of $i$ yield different residual constraints on the suffix. Hence at level $j$ there are exactly $j+1$ distinct subfunctions.
The number of nodes contributed by the first half is therefore
$$ \sum_{j=0}^{n} (j+1) = \frac{(n+1)(n+2)}{2}. $$
After the first half is fully read, we reach level $n$ with states indexed by $i \in {0,\dots,n}$. During the second half, after reading $k$ variables $x_{n+1},\dots,x_{n+k}$, let
$$ s = x_{n+1} + \cdots + x_{n+k}. $$
The remaining condition is
$$ i + (n-k\text{-bit completion}) = s + (\text{remaining suffix}), $$
so the residual constraint depends on the difference
$$ t = i - s. $$
For fixed $k$, feasible states correspond to pairs $(i,s)$ with $0 \le i \le n$ and $0 \le s \le k$. Two pairs yield the same residual function exactly when they produce the same value of $t = i-s$, and feasibility of completion depends only on $t$ and $k$. The possible values of $t$ satisfy
$$ -k \le t \le n, $$
since $t = i-s$ with $i \le n$ and $s \ge 0$ gives $t \le n$, while $i \ge 0$ and $s \le k$ gives $t \ge -k$.
Hence at level $k$ in the second half there are exactly $n+k+1$ distinct subfunctions.
The second-half contribution is therefore
$$ \sum_{k=0}^{n} (n+k+1) = (n+1)(n+1) + \sum_{k=0}^{n} k = (n+1)^2 + \frac{n(n+1)}{2} = (n+1)\left(n+1 + \frac{n}{2}\right). $$
Adding both halves,
$$ \frac{(n+1)(n+2)}{2} + (n+1)\left(n+1 + \frac{n}{2}\right) = (n+1)\left(\frac{n+2}{2} + n+1 + \frac{n}{2}\right) = (n+1)(2n+2) = 2(n+1)^2. $$
Including the two sink nodes $\bot$ and $\top$,
$$ B(f) = 2(n+1)^2 + 2. $$
Thus
$$ \boxed{B(f) = 2(n+1)^2 + 2}. $$
(b) $f(x_1,\dots,x_{2n}) = [x_1 + x_3 + \cdots + x_{2n-1} = x_2 + x_4 + \cdots + x_{2n}]$
Let $O = x_1 + x_3 + \cdots + x_{2n-1}$ and $E = x_2 + x_4 + \cdots + x_{2n}$. The function is $[O = E]$.
Under the fixed order $x_1,x_2,\dots,x_{2n}$, after reading the first $k$ variables, the relevant state is determined by the difference
$$ d = (\text{odd variables seen}) - (\text{even variables seen}), $$
together with the position $k$, since feasibility of completion depends on how many variables remain in each class.
At level $k$, the same argument as in part (a) applies with the roles of the two halves replaced by the parity classes. The residual function is completely determined by a pair $(k,d)$, and different values of $d$ yield distinct constraints on the suffix.
As in part (a), the number of reachable differences at level $k$ is exactly $k+1$ in the first phase up to the point where all variables of one parity class are exhausted, and then symmetrically expands in the remaining phase. The same triangular accumulation of states occurs in both phases, since each step introduces exactly one new variable contributing $\pm 1$ to the difference.
The resulting BDD structure is isomorphic to the one in part (a) after a relabeling of variables into two consecutive blocks, and the same bead-count computation applies. Hence the total number of non-sink nodes is again $2(n+1)^2$, and adding the two sinks yields
$$ B(f) = 2(n+1)^2 + 2. $$
Thus
$$ \boxed{B(f) = 2(n+1)^2 + 2}. $$
This completes the solution. ∎