TAOCP 7.1.4 Exercise 109

Section 7.1.4: Binary Decision Diagrams

Exercise 109. ▶ [HM17] [HM17] Continuing exercise 108, show that almost all Boolean functions of n var- iables have B(f π) > 2n/(n + 1/ln 2), for all permutations π of {1, . . . , n}, as n →∞.

Verified: no
Solve time: 4m17s

Solution

Let the current composition of $n$ be

$$ s_1 s_2 \cdots s_j, $$

and let

$$ C = \binom{n}{s_1,\dots,s_j} = \frac{n!}{s_1!\cdots s_j!}. $$

The generation procedure from Exercise 7.2.1.1.12 visits compositions by loopless moves in which a single unit is transferred between two adjacent parts, so that exactly one index $i$ is affected at each step. Each transition replaces a local pair

$$ (\dots, s_i, s_{i+1}, \dots) $$

by either

$$ (\dots, s_i-1, s_{i+1}+1, \dots) $$

or the reverse operation, while all other components remain unchanged.

Assume the move decreases $s_i$ by $1$ and increases $s_{i+1}$ by $1$. Let $C'$ denote the updated multinomial coefficient. Only factorials of $s_i$ and $s_{i+1}$ change, so

$$ C' = \frac{n!}{(s_1!\cdots (s_i-1)!,(s_{i+1}+1)!\cdots s_j!)}. $$

Dividing by $C$ gives

$$ \frac{C'}{C} = \frac{s_i! , s_{i+1}!}{(s_i-1)!,(s_{i+1}+1)!}. $$

Using $s_i! = s_i (s_i-1)!$ and $(s_{i+1}+1)! = (s_{i+1}+1)s_{i+1}!$ yields

$$ \frac{C'}{C} = \frac{s_i}{s_{i+1}+1}. $$

Hence the update rule for a forward transfer is

$$ C \leftarrow C \cdot \frac{s_i}{s_{i+1}+1}. $$

If the inverse move is performed, increasing $s_i$ by $1$ and decreasing $s_{i+1}$ by $1$, the same identity applied in reverse gives

$$ C \leftarrow C \cdot \frac{s_{i+1}}{s_i+1}. $$

The initial composition is $(n)$, for which $C = 1$. Each subsequent composition is obtained by a single adjacent transfer, so maintaining $C$ requires only the corresponding multiplicative update at each visit, with no recomputation of factorials or global products.

This completes the computation rule for $C$ during loopless generation of compositions. ∎