# Errata

## Report errata.

If you discover a typo or error, please fill out this errata submission form. We appreciate your feedback.

## Errata.

Please see this list for the errata reported before June 2010. Here are the errata that have been reported since November 2011. For brevity, we have suppressed the spelling and grammatical errors. This list is for errors in the text. Errors in web content are just fixed when reported; errata in lectures are listed here.

**9.**Coefficient in third term on line 5 should be 1/12 (Steve Kroon 10/4/13)**32.**Last two elements in $G^[3]$ are incorrect (missing root nodes in inner sequences). (Santiago Castro, 3/22/14)**44.**Add the condition that $gcd(\cal T) = 1$ on line 4. (Pablo Rotondo, 6/8/14)**47.**Replace $z^{r+2}$ by $z^{r+1}$ in Figure I.9 (Jonathan Woodworth, 12/19/11)**61.**Is this a counterexample? Let the language consist of one word, aaa. Then the generating function is $L(z)=z^3$, so $L'(z)=3z^2$, so $(1/2)L'(1/2) = 3/8$. The example states that this is the expected time for the first occurrence of aaa, but of course that is wrong, since the expected time cannot be less than 1. (Miklos Bona, 1/12/18)**74.**One step missing in Figure at line -6. The step "=1" should be "+1" and "+0" (Shingo Saito, 1/28/15)**77.**In I.48, $\kappa(\tau)$ should be $\kappa(\bullet)$ (Shingo Saito, 1/28/15)**79.**In Defintion I.13, $\mathcal T$ should be $\mathcal C$ in thefirst line and the last line should end with $\mathcal L\cong\mathcal C$ (Shingo Saito, 1/28/15)**85.**The formula for the example $Z(S_m)$ is wrong in Note I.58 (it should be a polynomial), so add the constraint $j_1+2j_2+\dots+mj_m=m$ to the sum (Bruno Salvy, 5/25/13)**86.**In displayed equation in I.60, $n/d$ -> $m/d$ (Shingo Saito, 1/28/15)**86.**Last line of Note I.60 needs recasting (especially fonts) (Bruno Salvy, 5/25/13)**87.**Formal definition of substitution would translate to $B(zC(z))$ and is incorrect. Should be $$ \sum_{k\geq 0} \sum\limits_{\beta \in \mathcal B_k}\epsilon_{\beta} \times \hbox{ Suc}_{k}(\mathcal C) $$ where each $\epsilon_\beta$ is a neutral class $\forall \ \beta \in \mathcal B$. (Ricardo Gomez, 9/17/13)**113.**Entry for $k=2$ in the table should be $6.22\times 10^{-56}$ (David Daniels, 7/22/13)**123.**$n^{1-1/r}$ -> $n^{n(1-1/r)}$ in the fourth line of Figure II.8 (Alejandro, 8/15/15)**136.**Formal definition of substitution is incorrect. See description of similar error for unlabelled objects on page 87. (Jason Gao, 2/22/14)**160.**$k$ should be $\ell$ and $\ell$ should be only $y\sqrt{\nu/2}$ when taking the limit in Note III.3 (Bruno Salvy, 5/25/13)**180.**$[z^n]e^z(2-e^z)^{-2}$ -> $[z^n](e^z-1)(2-e^z)^{-2}$ in numerator of displayed equation in III.14. (Pablo Rotondo and Santiago Castro, 6/6/14)**200.**"iterate of $u$" -> "iterate of $\sigma$" on line 3. (Jason Gao, 2/22/14)**200.**$a(u):=zu+F(z,1)/(1-zu)$ -> $a(u)=zu+zuF(z,1)/(1-zu)$ on line 23. (Jason Gao, 2/22/14)**201.**Missing "+1" in expression for $K(z,u)$ in III.32. (Pablo Rotondo, 6/7/14)**216.**In line -5, "equals b" -> "equals h". (Sergey Dovgal, 9/7/17)**236.**In line 7, $I_{2m}$ should be $I_m$. (Shingo Saito, 1/28/15)**242.**Exponent should be $n-m$ rather than $m-n$ in lines 8 and 11. (Shingo Saito, 2/3/15)**246.**Better to specify the restriction that $f(z)$ has nonnegative real coefficients (David Daniels, 9/11/13)**256.**$\alpha_1^{-n+r}$ should be $\alpha_1^{-n-r}$ on line -4 (David Daniels, 9/10/13)**256.**$z-\alpha_1$ -> $\alpha_1 - z$ on line -4 (Miklos Bona, 2/27/18)**260.**After (32), should be $R^*(z) = 1/(2+z-e^z)$ . (Sergey Dovgal, 9/7/17)**295.**$n/2$ -> $n/4$ and $n/4$ -> $n/8$ on line 21 (Antonio Vera, 5/25/13)**314.**Denominator in Answer(Q) code should be $(1/q -1)$ (Joseph Tassarotti, 9/8/17)**314.**RHS of (34) should read $n(1/q -1) + 1$ (Pablo Rotondo, 10/22/14)**332.**Missing comma in weights heading in Figure V.11. (Sergey Dovgal, 9/7/17)**338.**Replace $z_m$ by $z_1$ and $z_m$ by $z_2$ in the first two columns of the bottom row in the determinant in V.27 (Mark Sellke, 12/5/11)**338.**Replace $z_i$ by $z_j$ at the end of the last line (Mark Sellke, 12/5/11)**390.**Thm VI.3 is stated for real $\alpha$ and $\beta$, but that assumption should be explicit in Cor VI.1 too. (Bruno Salvy, 5/25/13)**403.**The expansion in the equation after (38) the expansion should read $$y - 1 = - \sqrt{2} (1 - ez)^{1/2} + \frac{2}{3} (1 - ez) + O((1 - ez)^{3/2}).$$ (Benjamin Hackl, 12/11/17)**407.**Replace $Y(Z)^{1/p}$ in the sentence before Equation (40) with $(Y(Z)/Z)^{1/p}$. [Details: as $Y(Z)$ is 0 for $Z = 0$, $Y(Z)^{1/p}$ cannot be analytic around $Z = 0$. Instead, the function $(Y(Z)/Z)^{1/p}$ should be investigated. This justifies that singularity analysis can be applied to $(Y(Z)/Z)^{1/p}$, and as there is the connection $y(z)/z = (Y(z^p)/z^p)^{1/p}$, we are allowed to translate the extracted coefficient growth of $(Y(Z)/Z)^{1/p}$ to the coefficient growth of $y(z)$.] (Benjamin Hackl, 12/11/17)**408.**"$\alpha \in\mathbb Z$" -> "$\alpha \in\mathbb C$" in the first line of Theorem VI.7. (Sebastian Wild, 9/21/15)**446.**$\Gamma(s)$ -> $\log\Gamma(s)$ on line -4 (Bruno Salvy, 5/25/13)**448.**"G" -> "K" on last line of the page (two instances) (Antonio Vera, 12/22/13)**446.**$g_{0,1}$ -> $g_{1,0}$ in (44) (Xing Shi Cai, 2/27/18)**475.**Replace $Y_{2n-1}$ by ${1\over 2}Y_{2n-1}$ on line 3 (Mark Ward 5/7/12)**475.**Replace 4 by $2^{7/4}$ on line 3 (Alex Daifotis, Nader Al-Naji, and Mark Ward 5/7/12)**496.**$y_1,(z)$ -> $y_1(z)$ on line -7 (Don Knuth, 9/29/14)**497.**Catalan curve should be smooth (replace low-res image) (Don Knuth, 9/29/14)**499.**"monomial ... is" -> "monomials ... are" on line 10 (Don Knuth, 9/29/14)**509.**"$c$ univariate" -> "$c$ unknown univariate" on line 8 (Don Knuth, 9/29/14)**509.**"F(z,u)" -> "F(z,0)" in the definition of $G_j(z)$ in (92) (Don Knuth, 9/29/14)**509.**"was not" -> "were not" in line following (92) (Don Knuth, 9/29/14)**509.**"which is rewritten as" -> "which is rewritten as a polynomial equation in $u$ with $z$ considered fixed:" in line following (93) and then "algebraic function" -> "algebraic function of $z$" three lines further down (Don Knuth, 9/29/14)**510.**"1 -" -> "1 =" in (94) (Don Knuth, 9/29/14)**510.**Use $G_j(z)$ notation from (92) in (94) and (95) (Don Knuth, 9/29/14)**510.**Add reference to [88] on line 7 (Don Knuth, 9/29/14)**510.**"can be regarded as" -> "is" in line following (95) (Don Knuth, 9/29/14)**510.**Discussion between (96) and Proposition VII.9 is unnecessary because the BGF in the bottom line of page 510 is an immediate consequence of (92) and (96), and then the formula for F(z) follows directly if we set $u=0$. (Don Knuth, 9/29/14)**510.**Add explanation of why the simultaneous linear equations in (94) have a solution: the matrix of coefficients can be converted to a Vandermonde determinant (involving the distinct functions $u_0$, \dots, $u_{c-1}$) by simple column operations. The matrix of coefficients for the case $c=3$ makes this point clear. (Don Knuth, 9/29/14)**513.**"---principal" -> "principal" on line 7 (Don Knuth, 9/29/14)**516.**$u = 1/(1-w)$ and $z = w(1-3w)$ in (VII.39) (Jason Gao, 8/17/17)**533.**$K_r$ -> $\Lambda_r$ in (145) (Bruno Salvy, 5/25/13)**534.**$3r-1$ -> $3r-4$ in (146) (Bruno Salvy, 5/25/13)**536.**Missing parens around $y(z) - y_h(z)$ in (149). (Sergey Dovgal, 9/7/17)**538.**Missing $n$ in fourth expression on line 7. (Sergey Dovgal, 9/7/17)**555.**Should be using big-Oh in (25)? (Sergey Dovgal, 9/7/17)**556.**$-n(\cos\theta_0 -1$ -> $n(\cos\theta_0 -1$ in (28) (Yucong Zhang, 8/14/18)**558.**missing factor of $\frac{1}{\sqrt{2\pi}}$ on right-hand side on line -18 (see (68)) (Mark Ward, 6/29/18)**559.**The inequalities hold, but both RHS expressions are off by a factor of 2 in (34). See Exercise 7.2.1.5--51 in Knuth, volume 4A (or page 53 of Volume 3). (Don Knuth, 2/19/15)**580.**Missing factor of $1/\sqrt{3}$ in formula for $R_n$ on line 13. See Mutafchiev and Kamenov,*Asymptotic formula for the number of plane partitions of positive integers*, Comptus Rendus-Academie Bulgare Des Sciences 59 (2006), no. 4, 361. (Suresh Govindarajan, 6/8/14)**587.**"VIII.46" -> "IV.46" on line 2. (Sergey Dovgal, 9/7/17)**605.**Replace 2 by $\sqrt3/(2\pi)$ in Proposition VIII.11 (Svante Janson, 11/14/11)**625.**$\frac{1}{2\pi T}$ -> $\frac{\pi}{2T}$ in (11) since the constant is $$ \frac{1}{2\pi} \int_{T\leq |t| \leq \pi} \frac{1}{|1-e^{it}|} dt \leq \frac{1}{2\pi} \int_{T\leq |t| \leq \pi} \frac{\pi}{2 |t|} \leq \frac{1}{4T} 2(\pi-T) \leq \frac{\pi}{2T}$$ (Daniel Krenn, 2/7/13)**630.**$g'(u_0 \tau_h)$ -> $\frac{u_0 g'(u_0 \tau_h)}{g'(\tau_h)}$ on line -15 (Daniel Krenn, 2/7/13)**637.**$W_1(z)$ -> $D(z)$ on line 16 (Xing Shi Cai, 1/11/19)**656.**Replace $z\le R$ by $|z|\le R$ and $\rho < r$ by $\rho < R$ on the third line of Theorem IX.9. (Clemens Heuberger, 4/14/14)**656.**"standard deviation" -> "variance" in the last sentence of Theorem IX.9. (David Bevan, 10/13/15)**657.**Equation (39): Second term should have a factor of 2. (Clemens Heuberger, 8/16/12)**657.**Equation (39): Sign error in fourth term? (Michael Albert, 9/27/17)**657.**Equation (40): First term should be negated. (Clemens Heuberger, 8/16/12)**657.**Equation after (41): First term should be negated. (Clemens Heuberger, 8/16/12)**668.**The outer arc is $\gamma_3$ and the linear parts are $\gamma_2$ and $\gamma4$ in lines 19--20 (Daniel Krenn, 2/7/13)**668.**$-1+n\Delta$ -> $n(\gamma-1)$ on line 22 (Daniel Krenn, 2/7/13)**668.**"decrease continuously from" -> "varies continuously between" on line 25 (Daniel Krenn, 2/7/13)**668.**Add constant factor $K$ to RHS of inequality on line -1 (Daniel Krenn, 2/7/13)**670.**$A<\alpha(1)+1/2$ on line 9, so $\alpha(1)\in\mathbb{R}$ should be assumed (at least in Theorem IX.11 on page 669) (Daniel Krenn, 2/7/13)**676.**"standard deviation" -> "variance" in the last sentence of Theorem IX.12. (David Bevan, 10/13/15)**678.**"standard deviation" -> "variance" in the penultimate sentence in the proof of Theorem IX.12. (David Bevan, 10/13/15)**682.**$(z,u)=(\rho,\tau)$ -> $(z,\tau)=(\rho,1)$ on line 23 (Daniel Krenn, 2/7/13)**686.**The notation used for the falling factorials, e.g. $(\alpha)_{(r)}$, is inconsistent with the falling factorials defined on p. 520 where they look like $\theta^{\underline{\ell}}$ (Daniel Krenn, 2/7/13)**686.**$n$ missing under $\sup$ on line 9 (Daniel Krenn, 2/7/13)**702.**As per (86), sign of second term in (97) should be + (Omer Angel and Andrew Rechnitzer, 8/23/17)**712.**$\cal M$ -> $\cal F$ on line 17 (Daniel Krenn, 2/7/13)**712.**$r_H$ -> $\rho_H$ and $r_G$ -> $\rho_G$ on line 21 (Daniel Krenn, 2/7/13)**738.**Replace 1 by the empty class in the pruned binary tree speficiation. (Antonio Vera, 4/5/13)**741.**Interchange the exponents l and m on line 4 (Tom Hillegers, 5/7/12)**752.**"height" -> "width" on line -9 (Antonio Vera, 4/5/13)**758.**$w^8$ -> $w^6$ on line 3 (Yucong Zhang, 8/14/18)**763.**H(x) is not a Heaviside function. "indicator kernel function"? (Sergey Dovgal, 9/7/17)**765.**$O(x^M)$ -> $O(x^{M-1})$ on line -2 (Richard Brent, 9/17/14)**796.**"Combinatorial Identities" -> "Introduction to Combinatorial Analyisis" in reference [513] (Allen Stenger, 8/29/15)