TAOCP 7.1.2 Exercise 45
The expression $n^2(n+1)^2\cdots (n+r-1)^2$ treats the construction of a Boolean chain as if step $i$ allows an arbitrary independent choice of an ordered pair of earlier objects, with $(n+i-1)$ avail...
Section 7.1.2: Boolean Evaluation
Exercise 45. [HM20] Why doesn't the proof of Theorem S simply argue that the number of ways to choose $j(i)$ and $k(i)$ so that $1 \le j(i), k(i) < i$ is $n^2(n+1)^2 \ldots (n+r-1)^2$?
Verified: yes
Solve time: 1m48s
Solution
The expression
$n^2(n+1)^2\cdots (n+r-1)^2$
treats the construction of a Boolean chain as if step $i$ allows an arbitrary independent choice of an ordered pair of earlier objects, with $(n+i-1)$ available objects at that moment.
The proof of Theorem S does not proceed in this way because the set of “available objects” at step $i$ is not a free collection of $(n+i-1)$ independent choices. Each object is a Boolean function produced by earlier steps, and different syntactic choices can define the same function.
At step $i$, selecting indices $j(i),k(i)$ together with a binary operator determines a new function $x_i = x_{j(i)} \circ x_{k(i)}$, but the mapping from index pairs to functions is not injective. Distinct pairs $(j,k)$ and $(j',k')$ can yield identical Boolean functions whenever the corresponding subfunctions agree pointwise or when the operator identifies inputs, as happens for commutative or idempotent operations such as $\wedge$ and $\vee$. Therefore counting index pairs counts syntactic descriptions rather than distinct constructions.
The multiplication argument also assumes independence between successive choices. This fails because the pool of previously constructed functions depends on earlier choices of $(j(t),k(t))$ for $t<i$. Two different histories can produce different labeled sets of intermediate results while generating the same collection of Boolean functions, so the factor $(n+i-1)^2$ does not represent a fixed combinatorial choice space.
Theorem S counts objects determined by their induced Boolean functions or equivalence classes of chains, not raw sequences of index selections. The naive product counts sequences of derivation steps, many of which collapse to the same chain or the same function after evaluation. This overcounting invalidates the direct product formula.
This completes the solution. ∎