TAOCP 7.1.4 Exercise 219

Exercise 219. [20] [20] What is Z(F) when F is the family (a) WORDS(1000); . . . ; (e) WORDS(5000)?

Verified: no
Solve time: 2m40s

We restart from the definition of the family and apply the ZDD reduction rules exactly as stated in TAOCP §7.1.4.

Let the ordered universe be $x_1, x_2, \ldots, x_n$. The family

$$ \mathrm{WORDS}(n) $$

is the family of all binary words of length $n$, equivalently the family of all subsets of ${x_1,\ldots,x_n}$. Thus every partial assignment to any subset of variables can be extended to a valid element of the family. In ZDD terms, no choice ever leads to exclusion of all completions.

Define $F_k$ to be the subfamily corresponding to variables $x_k, x_{k+1}, \ldots, x_n$. For $\mathrm{WORDS}(n)$, we have for every $k$,

$$ F_k = \mathcal{P}({x_k,\ldots,x_n}), $$

the full power set. In particular, $F_k$ does not depend on whether $x_k$ is included or excluded.

At a decision node labeled $x_k$, the ZDD construction gives:

$$ \mathrm{low}(v_k) = F_{k+1}, \quad \mathrm{high}(v_k) = F_{k+1}. $$

Thus the 0-branch and 1-branch are identical.

Now we apply the fundamental ZDD reduction rule:

If a node has identical 0-child and 1-child, it is eliminated and replaced by that child.

Therefore every node labeled by any $x_k$ is eliminated, since both outgoing edges point to the same subfamily $F_{k+1}$. This argument applies inductively from $k=n$ down to $k=1$, so all internal nodes disappear.

We are left only with the terminal representing the full family. The family $\mathrm{WORDS}(n)$ contains all subsets, so it corresponds to the terminal $\top$.

No node labeled by a variable can remain in a reduced ordered ZDD, since any such node would violate reduction by having identical children. Hence the reduced diagram consists of exactly one node, the terminal $\top$.

Therefore,

$$ Z(\mathrm{WORDS}(n)) = 1. $$

There is no contribution from $\bot$, since no assignment is excluded, so $\bot$ is not reachable and is not part of the reduced diagram for this family.

Finally, applying this to each requested value:

$$ Z(\mathrm{WORDS}(1000)) = Z(\mathrm{WORDS}(2000)) = Z(\mathrm{WORDS}(3000)) = Z(\mathrm{WORDS}(4000)) = Z(\mathrm{WORDS}(5000)) = 1. $$

Hence the answers are

$$ \boxed{1,\ 1,\ 1,\ 1,\ 1}. $$