Errata

Report errata.

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

Errata list for the lecture slides.

This list is under construction. Many errors are noted in the weekly e-mails in the "Online Course Materials" page and have not been moved here yet.

Lecture 5, slide 46 "multiplicity 5" -> "multiplicity 4"
Lecture 6, slide 45 add condition "and total number of 0s is one greater than total number of 1s" to the definition of U
Lecture 6, slide 45 add condition "and total number of 1s is one greater than total number of 0s" to the definition of D
Lecture 7, slide 17 exponent of $N$ should be $\alpha -1$ not $1-\alpha$
Lecture 7, slide 24 $\beta$ should be $-3/4$ not $3/4$
Lecture 7, slide 40 second condition should be $\Phi(0,0) = 0$ not $\Phi(0,0)\ne 0$

Errata list for the book.

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.

9. Coefficient in third term on line 5 should be 1/12 (Steve Kroon 10/4/13)
29. Summation in line 10 should be over j instead of k (Mohit Gurumukhani 12/4/19)
32. Last two elements in $G^[3]$ are incorrect (missing root nodes in inner sequences). (Santiago Castro, 3/22/14)
33. "recursive is" -> "recursive if" on line -14 (Michael Wallner, 6/13/20)
33. Replace $\Xi_i$ by $\Phi_i$ on line -17 (Michael Wallner, 6/13/20)
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)
63. "n=6" -> "n=8" on line 1 (Yanning Yang, 3/22/21)
74. One step missing in Figure at line -6. The step "=1" should be "+1" and "+0" (Shingo Saito, 1/28/15)
76. "will" -> "with" on line -14 (Michael Wallner, 6/13/20)
77. In I.48, $\kappa(\tau)$ should be $\kappa(\bullet)$ (Shingo Saito, 1/28/15)
79. In Definition I.13, $\mathcal T$ should be $\mathcal C$ in the first line and the last line should end with $\mathcal L\cong\mathcal C$ (Shingo Saito, 1/28/15)
79. On line 12, "binary trees" -> "binary trees where the size function is the number of external nodes" (Yanning Yang, 5/21/20)
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)
139. In the last paragraph of Note II.28 "whole symmetric group" -> "whole symmetric group or the alternating group" and "classification of groups" -> "classification of finite simple groups". (Doug Shors, 1/24/21)
148. 18 -> 93 on last line of figure caption (Yanning Yang, 11/1/20)
148. "2. Sets, multisets" -> "2. Sequences, sets" in Figure II.18 (Yanning Yang, 3/22/21)
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)
174. $1/G_n$ factor missing following the second equal sign on line 2. (Yanning Yang, 7/13/20)
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)
188. "$\ell_k$" -> "$\ell_n$" in two places on the last display, $g_k/k!$ -> $g_n/n!$ in the last factor of the product, and $\ldots + \ell_k = k$ -> $\ldots + \ell_n = n$ and $\ldots + \ell_k$ -> $\ldots + \ell_n$ on the line following. (Bernhard Gittenberger, 6/21/10)
189. "monomial" -> "complete" on line 6 (Álvar Ibeas, 9/5/20)
189. In the expressions for $a_n$ and $b_n$ on line 10, all occurrences of $i_r$ should be $i_n$ and in the expression for $c_n$, $x_i^r$ should be $x_i^n$. (Yanning Yang, 6/26/20)
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)
201. $A$ -> $B$ on line -2. (Yanning Yang, 6/26/20)
206. $2r(2r-1)^n$ -> $2r(2r-1)^{n-1}$ on line 10. (Yanning Yang, 6/26/20)
209. "of size" -> "of size $n$" on line 14. (Yanning Yang, 6/26/20)
210. $\ell+1$ -> $\ell$ above (76). (Yanning Yang, 6/26/20)
210. $(1-z)(v+1)$ -> $1-z$ on line -10. (Yanning Yang, 6/26/20)
212. 61 -> 60 on line 9 (Yanning Yang, 11/23/20)
213. Middle term should be negated on line 10. (Yanning Yang, 6/26/20)
213. $p_{i+1}p_{i+2}\ldots p_k$ -> $p_{k-i+1}\ldots p_k$ in definition of $\Gamma$ on line -14 (see definition of $c_i$ on page 60). (Yanning Yang, 6/26/20)<
215. $SET_m$ -> $SEQ_m$ on line 14. (Yanning Yang, 6/26/20)
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)
245. Missing ) on last line of Fig. IV.5 (Yanning Yang, 11/23/20)
246. Better to specify the restriction that $f(z)$ has nonnegative real coefficients (David Daniels, 9/11/13)
255. $1-$ -> $1+$ on line 3 (Yanning Yang, 11/23/20)
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)
267. $n_i-n_j$ -> $n_1-n_2$ on line 1 (Yanning Yang, 12/15/20)
267. "0.8" -> "0.9" in figure caption (Yanning Yang, 3/22/21)
280. Relace $y$ by $w$ on rhs of equation at the end of Note IV.47 (Yanning Yang, 12/15/20)
283. "(3/2)" -> "(2/3)" on line 5 (Yanning Yang, 3/22/21)
294. $\rho$ -> $\sigma$ on line -8 (Yanning Yang, 12/15/20)
295. $\rho$ -> $\sigma$ on line 8 (Yanning Yang, 12/15/20)
295. $n/2$ -> $n/4$ and $n/4$ -> $n/8$ on line 21 (Antonio Vera, 5/25/13)
295. $F(z, u)$ -> $F^{\langle k\rangle}(z, u)$ on line -6 (Yanning Yang, 12/15/20)
297. "partitions" -> "compositions" on line -1 (Yanning Yang, 4/15/21)
307. "equivalent" -> "equivalence" on line 4 of V.10 (Michael Wallner, 6/13/20)
308. Line -4 should end with "have shown that $[z^n] M(z) \sim K \alpha^n n^{\ell-1}$, for $K, \alpha > 0$, where $\ell$ is the multiplicity of the dominant pole $1/\alpha$ of $M(z)$" (Cyril Banderier and Massimiliano Goldwurn, 11/29/19)
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)
320. Add comma before "ceiling" on line 2 after (49) (Michael Wallner, 6/13/20)
321. "321" -> "322" on line 2 (Yanning Yang, 4/15/21)
321. "ceiled" -> "floored" on line -7 (Yanning Yang, 4/15/21)
330. Missing space after "Equations" on line 8 (Michael Wallner, 6/13/20)
332. Missing comma in weights heading in Figure V.11. (Sergey Dovgal, 9/7/17)
334. "that satisfies" -> "satisfying" on line -4 (Michael Wallner, 6/13/20)
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)
344. $T=(T_{i,j})$ -> $T=(t_{i,j})$ in (87) (Michael Wallner, 6/13/20)
345. Replace $w$ by $v$ in both instances on the top line of (90) (Jin Soo Ihm, 5/7/20)
384. "dt" -> "dx" on line -10 (Yanning Yang, 4/15/21)
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)
391. First integral in (2) needs a $1/n$ factor because of the change of variable. (Jin Soo Ihm, 5/8/20)
391. $-n$ should be $-n-1$ in the exponent in the definition of $J_n$ on line -10. (Jin Soo Ihm, 5/8/20)
393. $z/\zeta$ -> $z\zeta$ on line -4 (Yanning Yang, 4/15/21)
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)
415. $g_{n,k}$ -> $g_{n}^{(k)}$ on line -7 (Michael Wallner, 6/13/20)
424. "integer" -> "integer $k$" on line 5 (Marcel Goh, 1/28/20)
441. "thay" -> "that" on line 9 (Michael Wallner, 6/13/20)
442. "polynomial" -> "polynomials" on line -19 (Michael Wallner, 6/13/20)
446. $\Gamma(s)$ -> $\log\Gamma(s)$ on line -4 (Bruno Salvy, 5/25/13)
446. $g_{0,1}$ -> $g_{1,0}$ in (44) (Xing Shi Cai, 2/27/18)
448. "G" -> "K" on last line of the page (two instances) (Antonio Vera, 12/22/13)
449. $G(z)$ -> $K(z)$ on line 8 of VII.3 (Michael Wallner, 6/13/20)
450. $\log{1\over 1-z}$ -> $\log{1\over 1-pz}$ in (16) (Jin Soo Ihm, 5/15/20)
469. Replace $r$ by $z_0$ and $s$ by $w_0$ throughout the proof (Valentin Feray, 1/6/21)
469. Replace $\sqrt{r-z}$ by $\sqrt{1-z/r}$ in display equation on line -7 (Valentin Feray, 1/6/21)
469. Replace $y_0$ by $w_0$ in display equation on line -14 (Adeline Peirrot, 4/19/21)
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)
588. Equation in the middle of the page should be $$J(\theta_1) = \frac{1}{2 \pi \zeta^N} \int_{-\theta_1}^{\theta_1} A(\zeta e^{i \theta}) B(\zeta e^{i \theta})^n e^{- i N \theta} d\theta$$ (Élie de Panafieu, 8/30/19)
589. Equation in Note VIII.37 should be $$[z^n] A(z) B(z)^n = \frac{B(\zeta)^n}{\zeta^N \sqrt{2 \pi n}} \left( c n^{-1} + O(n^{-2}) \right)$$ where $$c = - \frac{\zeta A'(\zeta) + \zeta^2 A''(\zeta)}{2 \phi_2^{3/2}} - \frac{i \phi_3 \zeta A'(\zeta)}{2 \phi_2^{5/2}}$$ with $$\phi_m = - \partial_{\theta = 0}^m \log \left( B(\zeta e^{i \theta}) \right) $$ for $m=2$ and $3$. (Élie de Panafieu, 8/30/19)
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)
660. $1 + 2c(1/2)$ -> $-1+2c(1/2)$ in Proposition IX.10 (Lucas Gerin, 4/10/19)
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)
708. Display equation in Proposition IX.22 should be $$\lim_{n\to\infty}\sqrt n P(X_n=x\sqrt n) = {x\over 2}e^{-x^2/4}$$(Markus Kuba, 4/23/20)
708. Footnote only holds for $1<\lambda<2$ with $x>0$ (Markus Kuba, 3/6/21)
709. The density in (102) for $1<\lambda<2$ is valid only for $x>0$ (the case of negative $x$ follows directly from the transformation in Feller) (Markus Kuba, 3/6/21)
709. Change summation index to $j$ in (102) since $k$ is used later (Markus Kuba, 4/23/20)
710. Change summation index to $j$ in (106) (Markus Kuba, 4/23/20)
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)
712. Need $\lambda^\prime=\lambda$ in case (ii) of Proposition IX.24 (for $\lambda^\prime<\lambda$ the probabilities for $P(X_n=k)$ decay at order $n^{-(\lambda-\lambda^\prime)} as pointed out by Noy and Gimenez (Markus Kuba, 3/6/21)
712. It seems that a bimodality phenomenon appears for $\lambda=\lambda^\prime$ in case (iii) of Proposition IX.24 (Markus Kuba, 3/6/21)
712. Replace first sentence after Proposition IX.24 with "No similar phenomena appear for $\lambda^\prime>\lambda$, except for the "small" range and $1>\lambda^\prime>\lambda$; otherwise, the distributions turn out to be purely discrete, similar to the Boltzmann type discrete limit law in the map-Airy case." (Markus Kuba, 3/6/21)
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)