TAOCP 7.1.4 Exercise 173
A Boolean function $f(x_1,\dots,x_n)$ is skinny if its reduced ordered binary decision diagram has exactly one branch node for each variable, and at every branch node exactly one of LO or HI is a sink...
Section 7.1.4: Binary Decision Diagrams
Exercise 173. ▶ [HM33] [HM33] Exactly how many Boolean functions f(x1, . . . , xn) are skinny after some reordering of the variables, f(x1π, . . . , xnπ)?
Verified: no
Solve time: 6m35s
Setup
A Boolean function $f(x_1,\dots,x_n)$ is skinny if its reduced ordered binary decision diagram has exactly one branch node for each variable, and at every branch node exactly one of LO or HI is a sink node. Reduction also requires that LO $\neq$ HI at every node.
A function is skinny after some reordering of variables if there exists a permutation $\pi$ of ${1,\dots,n}$ such that $f(x_1^\pi,\dots,x_n^\pi)$ has a skinny BDD in the sense above.
The task is to determine the number of Boolean functions $f(x_1,\dots,x_n)$ with this property.
Solution
Fix a permutation $\pi$ of ${1,\dots,n}$. Consider skinny BDDs whose variable order is exactly $x_{\pi_1},\dots,x_{\pi_n}$. Such a BDD is a directed chain of $n$ branch nodes, since each variable appears exactly once.
Let the nodes along this chain be $v_1,\dots,v_n$, where $v_i$ queries $x_{\pi_i}$. For each $i<n$, exactly one outgoing edge of $v_i$ goes to a sink and the other goes to $v_{i+1}$. This choice can be made in two ways: either LO leads to the next variable and HI goes to a sink, or HI leads to the next variable and LO goes to a sink.
Independently, the sink value on the terminating edge at each $v_i$ for $i<n$ may be chosen freely in ${0,1}$, since both assignments preserve validity of the BDD structure. Thus each internal node contributes $2\cdot 2=4$ possibilities.
At the final node $v_n$, both children are sinks. Reduction requires LO $\neq$ HI, so the pair of sink values must be either $(0,1)$ or $(1,0)$, giving exactly $2$ possibilities.
For a fixed permutation $\pi$, the number of skinny BDDs is therefore
$4^{n-1}\cdot 2 = 2^{2n-2}\cdot 2 = 2^{2n-1}.$
Each such BDD defines a distinct Boolean function, since the evaluation path is uniquely determined by the ordered sequence of variable tests and sink labels.
It remains to count functions that are skinny for some permutation. The structure of a skinny BDD determines a unique variable ordering: the root variable is the only one whose removal yields a subfunction depending on the remaining variables in a chain form, and induction fixes the entire order uniquely. Hence a function cannot admit two different variable orders that produce a skinny BDD without inducing identical ordered dependency structure, which would contradict the uniqueness of reduced ordered representations.
Therefore each Boolean function counted arises from exactly one permutation $\pi$, and no overcount occurs across different permutations.
Multiplying by the $n!$ possible permutations gives
$n!\cdot 2^{2n-1}.$
Thus the number of Boolean functions that are skinny after some reordering of variables is
$\boxed{n!,2^{2n-1}}.$
Verification
Each internal node contributes independently a choice of which edge continues and a choice of sink value, giving $4^{n-1}$ possibilities, since there are $n-1$ internal nodes. The last node contributes exactly $2$ possibilities because LO and HI must be distinct sinks. The total $4^{n-1}\cdot 2$ simplifies to $2^{2n-1}$. The dependence on variable order is a bijection between permutations and skinny structures, so multiplying by $n!$ counts each function exactly once.
This completes the proof. ∎