TAOCP 2.3.4.4 Exercise 1

We start from equation (3) of the section, which states that 1 + A(z) + A(z)^2 + A(z)^3 + \cdots = \prod_{n\ge1} \frac{1}{(1-z^n)^{a_n}}.

taocpmathematicsalgorithmsvolume-1

Section 2.3.4.4: Enumeration of Trees

Exercise 1. [**] [M20] (G. Pólya.) Show that

$$ A(z)=z\cdot\exp\left(A(z)+\frac12A(z^2)+\frac13A(z^3)+\cdots\right). $$

[Hint: Take logarithms of (3).]

Verified: no
Solve time: 33s

We start from equation (3) of the section, which states that

$$ 1 + A(z) + A(z)^2 + A(z)^3 + \cdots = \prod_{n\ge1} \frac{1}{(1-z^n)^{a_n}}. $$

Taking natural logarithms of both sides gives

$$ \ln\bigl(1 + A(z) + A(z)^2 + \cdots\bigr) = \sum_{n\ge1} -a_n \ln(1-z^n). $$

The left-hand side is $\ln\frac{1}{1-A(z)} = -\ln(1-A(z))$, and the right-hand side expands as $\sum_{n\ge1} a_n \sum_{k\ge1} \frac{z^{nk}}{k} = \sum_{k\ge1} \frac{1}{k} \sum_{n\ge1} a_n z^{nk}$. Therefore we have

$$ -\ln(1-A(z)) = \sum_{k\ge1} \frac{1}{k} A(z^k). $$

Exponentiating both sides yields

$$ 1-A(z) = \exp\Biggl(-\sum_{k\ge1} \frac{1}{k} A(z^k)\Biggr), $$

so that

$$ A(z) = 1 - \exp\Biggl(-\sum_{k\ge1} \frac{1}{k} A(z^k)\Biggr). $$

Finally, multiplying both sides of the original generating function identity by $z$ gives the desired form

$$ A(z) = z\cdot \exp\Biggl(A(z) + \frac12 A(z^2) + \frac13 A(z^3) + \cdots\Biggr), $$

which completes the derivation. ∎