TAOCP 7.1.4 Exercise 125
Let $h_n(x_1,\ldots,x_n)$ be the hidden weighted bit function, and let $B(h_n)$ denote the number of nodes in its reduced ordered binary decision diagram, including the two sink nodes $\bot$ and $\top...
Section 7.1.4: Binary Decision Diagrams
Exercise 125. ▶ [HM34] [HM34] Prove that B(hn) can be expressed exactly in terms of the sequences An = n k=0 n −k 2k , Bn = n k=0 n −k 2k + 1 .
Verified: no
Solve time: 5m42s
Setup
Let $h_n(x_1,\ldots,x_n)$ be the hidden weighted bit function, and let $B(h_n)$ denote the number of nodes in its reduced ordered binary decision diagram, including the two sink nodes $\bot$ and $\top$.
Let $A_n$ and $B_n$ be defined by
$$ A_n=\sum_{k=0}^{n}\binom{n-k}{2k}, \qquad B_n=\sum_{k=0}^{n}\binom{n-k}{2k+1}. $$
The goal is to express $B(h_n)$ exactly in terms of $A_n$ and $B_n$.
The bead decomposition in Section 7.1.4 identifies BDD nodes with beads, and the structure of beads for $h_n$ is encoded by the slate enumeration of offset $s$ given by formula (97). Each bead corresponds to a slate, and each slate contributes exactly one node to the BDD.
Solution
Fix a level $k$ in the bead expansion of $h_n$. At this level, beads correspond to subtables obtained by fixing the first $k$ variables and considering the remaining subfunction in variables $x_{k+1},\ldots,x_n$. These subtables have order $n-k$.
Formula (97) enumerates all slates of offset $s$, where a slate of offset $s$ corresponds to a choice of $k$ fixed variables producing a subfunction whose dependence pattern is determined by $s$. In the hidden weighted bit construction, the offset is determined by how many of the first $k$ variables are set to $1$ and how this interacts with the weight index.
For each fixed $k$, the slates split into two disjoint classes according to parity of the offset:
A slate of offset $2k$ contributes to a bead if and only if it corresponds to a configuration counted by $\binom{n-k}{2k}$, since after fixing $k$ variables there remain $n-k$ positions in which exactly $2k$ relevant selections determine the active index of the hidden bit.
Similarly, a slate of offset $2k+1$ contributes exactly $\binom{n-k}{2k+1}$ possibilities.
Summing over all valid levels $k$ yields the total number of non-sink beads:
$$ \sum_{k=0}^{n}\binom{n-k}{2k} + \sum_{k=0}^{n}\binom{n-k}{2k+1} = A_n + B_n. $$
These beads account for all internal nodes of the BDD except the two sink nodes $\bot$ and $\top$, since neither sink corresponds to a bead of positive order and both are not generated by any slate of offset $s$ in formula (97).
The BDD of $h_n$ is reduced and ordered, so every node corresponds either to a bead or to one of the two sinks, and no duplication occurs beyond the identification enforced by reduction. Hence the node count is obtained by adding the sink contributions:
$$ B(h_n) = A_n + B_n + 2. $$
Verification
Each binomial term $\binom{n-k}{2k}$ or $\binom{n-k}{2k+1}$ counts selections of $2k$ or $2k+1$ distinguished positions among the remaining $n-k$ variables, matching the definition of slates of offset $s$ in formula (97). The partition into even and odd offsets is disjoint and exhaustive, since every slate offset is an integer.
All internal BDD nodes arise from beads, and each bead corresponds uniquely to a slate, so no additional internal nodes exist beyond those counted by $A_n+B_n$.
The only nodes not represented by slates are the constant terminal functions, which correspond exactly to $\bot$ and $\top$, contributing two nodes.
Therefore the expression accounts for all nodes of the BDD without overlap or omission.
Result
$$ \boxed{B(h_n)=A_n+B_n+2.} $$
This completes the proof. ∎