TAOCP 7.1.4 Exercise 259

Section 7.1.4: Binary Decision Diagrams

Exercise 259. ▶ [25] [25] A sequence of parentheses can be encoded as a binary string by letting 0 represent ‘(’ and 1 represent ‘)’. For example, ())(() is encoded as 011001. Every forest of n nodes corresponds to a sequence of 2n parentheses that are properly nested, in the sense that left and right parentheses match in the normal way. (See, for example, 2.3.3–(1) or 7.2.1.6–(1).) Let Nn(x1, . . . , x2n) = [x1 . . . x2n represents properly nested parentheses]. For example, N3(0, 1, 1, 0, 0, 1) = 0 and N3(0, 0, 1, 0, 1, 1) = 1; in general, Nn has Cn ≈ 4n/(√π n3/2) solutions, where Cn is a Catalan number. What are B(Nn) and Z(Nn)?

7.1.4 BINARY DECISION DIAGRAMS 279

Verified: no
Solve time: 53s