TAOCP 7.1.4 Exercise 175
Let a Boolean function on $n$ variables be represented by a reduced ordered BDD in the sense of Section 7.
Section 7.1.4: Binary Decision Diagrams
Exercise 175. [M30] [M30] Continuing exercise 174, find a way to enumerate the Boolean functions whose BDD contains exactly bj−1 nodes labeled j j , given a profile (b0, . . . , bn−1, bn).
Verified: no
Solve time: 6m42s
Setup
Let a Boolean function on $n$ variables be represented by a reduced ordered BDD in the sense of Section 7.1.4. Let level $j$ denote all nodes labeled $x_j$, so every node at level $j$ has LO and HI successors in levels $>j$ or at sinks $\bot,\top$.
Let $(b_0,b_1,\dots,b_n)$ be a profile such that $b_{j-1}$ is the number of nodes labeled $j$ for $1\le j\le n$. Let $N_j$ denote the number of available nodes that can serve as targets of edges from level $j-1$, meaning all nodes in levels $j,j+1,\dots,n$ together with the two sinks.
Thus $N_{n+1}=2$ and, for $1\le j\le n$, we have
$$ N_j = 2 + \sum_{k=j-1}^{n-1} b_k. $$
Each node at level $j$ is determined by an ordered pair $(u,v)$ with $u\ne v$, where $u$ is the LO successor and $v$ is the HI successor, both chosen from the set of size $N_{j+1}$.
Let $P_j$ denote the set of all admissible ordered pairs at level $j$, so
$$ P_j = {(u,v): u,v\in \mathcal{N}{j+1},\ u\ne v}, \quad |P_j| = N{j+1}(N_{j+1}-1). $$
Reducedness implies that all nodes at level $j$ correspond to distinct pairs in $P_j$, and no duplication of triples $(j,u,v)$ occurs.
Solution
Fix the levels from $n$ downward. At level $n$, successors must lie in level $n+1$, which contains only $\bot,\top$. Hence $N_{n+1}=2$, and
$$ |P_n| = 2\cdot 1 = 2. $$
A node at level $n$ is determined by choosing one ordered pair from these two possibilities. Reducedness forces all $b_{n-1}$ nodes at level $n$ to be distinct, so the number of ways to choose level $n$ is
$$ \binom{2}{b_{n-1}}. $$
Assume inductively that levels $j+1,\dots,n$ have been fixed, determining $N_{j+1}$. Then every node at level $j$ must choose its LO and HI successors from a set of size $N_{j+1}$, giving $|P_j|=N_{j+1}(N_{j+1}-1)$ possible distinct node types.
Reducedness at level $j$ forbids repetition of identical triples, so the $b_{j-1}$ nodes at level $j$ correspond to a choice of a $b_{j-1}$-subset of $P_j$, contributing
$$ \binom{N_{j+1}(N_{j+1}-1)}{b_{j-1}} $$
possibilities.
After selecting all nodes at level $j$, these nodes become available as targets for higher levels, so the recursion for available nodes becomes
$$ N_j = N_{j+1} + b_{j-1}. $$
Iterating from $j=n$ down to $j=1$ yields a product structure, since choices at distinct levels are independent once the target sets are fixed. The total number of BDDs with profile $(b_0,\dots,b_n)$ is therefore
$$ \prod_{j=1}^{n} \binom{N_{j+1}(N_{j+1}-1)}{b_{j-1}}, \quad N_{n+1}=2,\quad N_j = 2+\sum_{k=j-1}^{n-1} b_k. $$
This expression enumerates exactly the Boolean functions whose BDD has $b_{j-1}$ nodes labeled $j$, since every admissible selection of node types uniquely determines all edges and thus uniquely determines the BDD by the bead-to-node correspondence in Section 7.1.4.
Verification
Each node at level $j$ is uniquely determined by its ordered pair of successors because node labels are fixed by level and reduction forbids duplicate triples. The count $N_{j+1}(N_{j+1}-1)$ enumerates all ordered pairs with distinct components, matching the LO/HI requirement.
The recursion for $N_j$ accounts for all nodes that can appear below level $j-1$, since only levels $j,\dots,n$ and sinks are reachable targets. No other nodes exist by the ordering constraint.
Independence across levels follows from the acyclic structure: edges from level $j$ never point to level $\le j$, so choices made at level $j$ do not affect admissibility within the same level or below it, except through the deterministic update of available targets.
Result
The number of Boolean functions whose BDD has exactly $b_{j-1}$ nodes labeled $j$ for $1\le j\le n$ is
$$ \boxed{ \prod_{j=1}^{n} \binom{N_{j+1}(N_{j+1}-1)}{b_{j-1}} \quad \text{where } N_{n+1}=2,\ N_j=2+\sum_{k=j-1}^{n-1} b_k }. $$
This completes the solution. ∎