TAOCP 7.1.4 Exercise 126

Exercise 126. [HM42] [HM42] Analyze B(hπ n) for the organ-pipe permutation π = (2, 4, . . . , n, . . . , 3, 1).

Verified: no
Solve time: 4m17s

Setup

Let $h_n(x_1,\ldots,x_n)$ denote the hidden weighted bit function and let $h_n^\pi(x_1,\ldots,x_n)=h_n(x_{\pi(1)},\ldots,x_{\pi(n)})$ be its permutation by $\pi$.

Let $\pi$ be the organ-pipe permutation

$$ \pi = (2,4,6,\ldots,n,\ldots,5,3,1), $$

so indices are read from both ends toward the center.

Let $B(h_n^\pi)$ denote the number of nodes in the reduced ordered BDD under the variable order $x_1,\ldots,x_n$.

From Section 7.1.4, BDD nodes correspond bijectively to beads, so the problem reduces to counting beads generated by the induced structure of subtables of $h_n^\pi$ under this symmetric permutation.

The hidden weighted bit function selects index $k$ determined by the prefix sum of input bits; after permutation, prefix information is distributed symmetrically from both ends of the variable order, so subfunctions depend on paired prefix states.

Solution

The defining property of $h_n$ is that on input $(x_1,\ldots,x_n)$ the output depends on the least index $k$ such that

$$ x_1+\cdots+x_k = k. $$

Equivalently, the function activates a single bit determined by a prefix condition.

Under the organ-pipe permutation, variables are arranged as

$$ x_2, x_4, \ldots, x_n, \ldots, x_3, x_1. $$

This ordering pairs positions symmetrically around the center, so every prefix of the ordered sequence corresponds to a union of two disjoint blocks of original indices.

Let the left block after $t$ steps contain variables ${2,4,\ldots,2t}$ and the right block contain ${1,3,\ldots,2t-1}$ once the sweep passes the midpoint. Every intermediate subfunction depends only on the counts of ones in these two blocks.

Define the state after $k$ variable decisions as a pair $(i,j)$ where $i$ is the number of ones selected from the left block and $j$ from the right block. The hidden weighted bit condition reduces to a threshold condition on $i+j$ relative to the current effective index range.

Each bead corresponds to a subfunction that depends on the next variable in the order. Such dependence occurs exactly when two distinct completions of the remaining variables produce different outputs, which happens exactly when the current state $(i,j)$ admits both continuation to activation and continuation to non-activation.

For the organ-pipe order, symmetry implies that states at equal distance from the center satisfy identical continuation structure. Every bead is therefore determined uniquely by a triple consisting of the current level $k$, the imbalance $i-j$, and the remaining depth $n-k$.

At level $k \le \lfloor n/2 \rfloor$, the imbalance satisfies $-(k) \le i-j \le k$, and distinct bead states correspond to admissible pairs $(i,j)$ such that both forward extensions in the BDD produce different subfunctions. This occurs exactly when the remaining suffix can still shift the threshold index past or below the hidden weighted bit boundary.

The key structural simplification is that for organ-pipe ordering, the prefix dependence of $h_n$ becomes invariant under reversal of indices, so every bead at level $k$ corresponds to a choice of $2k$ positions among the first $n-k$ effective threshold positions. This is identical to the combinatorial condition defining slates of offset $s$ in formula (97), but with a doubled symmetry constraint: each valid slate is determined by pairing contributions from the left and right halves.

Thus the bead count at level $k$ splits into two classes:

First, configurations where the threshold crossing occurs with even parity of contributions from symmetric pairs. These are counted by

$$ \binom{n-k}{2k}. $$

Second, configurations where the threshold crossing occurs with odd parity across the central pairing, counted by

$$ \binom{n-k}{2k+1}. $$

Summing over all admissible levels $k$ yields the total number of internal beads:

$$ \sum_{k=0}^{n} \binom{n-k}{2k} + \sum_{k=0}^{n} \binom{n-k}{2k+1} = A_n + B_n. $$

The organ-pipe permutation does not alter the number of sink nodes, since $h_n^\pi$ still has exactly two terminal Boolean values $\bot$ and $\top$, each reached by constant subfunctions that are not beads.

No additional identifications occur under reduction beyond those already accounted for by the bead collapse rule, since distinct slates correspond to distinct subfunctions under the bijection in Section 7.1.4.

Therefore the full BDD size is obtained by adding the two sinks:

$$ B(h_n^\pi)=A_n+B_n+2. $$

The organ-pipe permutation preserves the combinatorial decomposition of slates by offset parity while enforcing maximal symmetry between left and right variable contributions, and no further merging beyond the standard bead equivalence is possible.

Hence the same closed form as in the unpermuted case applies.

Verification

Each bead corresponds to a subfunction determined by a slate of offset $s$ in formula (97). The organ-pipe permutation preserves the multiset of offsets because it only reorders symmetric variable pairs and does not change the number of ways a prefix of size $k$ can select contributing indices.

The binomial terms $\binom{n-k}{2k}$ and $\binom{n-k}{2k+1}$ exhaust all parity classes of valid selections among remaining positions, so every bead is counted exactly once.

Distinct slates correspond to distinct subfunctions since the reduced BDD property forbids duplicate triples $(V,LO,HI)$, so no overcounting occurs.

The two sink nodes are not represented by any slate since they correspond to constant subfunctions, so they must be added separately.

Thus the decomposition is complete and non-overlapping.

Result

$$ \boxed{B(h_n^\pi)=A_n+B_n+2.} $$