 # Concrete Mathematics, Second Edition

by Ronald L. Graham, Donald E. Knuth, and Oren Patashnik (Reading, Massachusetts: Addison-Wesley, 1994), xiii+657pp.

Here is a list of all significant changes that were made between January 1998 and May 2013. An asterisk (*) marks technical errors that are not merely typographical:

*page vi, line 9 from the bottom
change "finite" to "definite"
page ix, line 5 from the bottom
change "paid to the first finder of any" to "conveyed to anyone who is the first to report any"
page 8, line 2 from the bottom
change "1" to "$1$"
page 14, line 10 from the bottom
change "$\gamma;" to "$\gamma.$" page 20, in 21 change m to q (four times) page 22, line 4 change "Greek letter$\sum$" to "Greek letter$\Sigma$" page 22, line 7 change "1" to "$1$" pages 28 and 29 (beginning with the 21st printing, recurrence (2.12) is changed to more realistic equations in which$C_1=0$and the summation rule is used only for$n>1$; this implies several dozen changes to the exposition; the previous form with$C_1=2$was inconsistent with real quicksort implementations) page 30 a new graffito near (2.16): "My other math books have different definitions for these laws." *page 36, line 13 change "$K(j)=J'(k)$be the basic" to "$K(j)$,$J'(k)$be sets that correspond to the basic" page 41, line 2 from the bottom change "at least seven" to "at least eight" page 43, line 16 change "the induction" to "the inductive step" page 44, line 10 change "first n integers" to "first few nonnegative integers" page 45, line 5 change "(2.41)" to "(2.40) and (2.41)" page 45, line 3 from the bottom change "between 0" to "between$0$" page 55, last three lines of Table 55 change$f$to$u$and$g$to$v$(12 changes) *page 58, line 20 change$\sum_{k=0}^{n}$to$\sum_{k=0}^{n-1}$page 60, line 7 change "or$x^-=0$" to "or$x^-=0$, or both" page 64, in exercise 26 change "double product" to "double product P=" page 65, exercise 31 change " Riemann's" to "Riemann's" page 71, line 13 from the bottom change "function with" to "function on an interval of the real numbers, with" page 71, bottom line change "$x$and$\lceil x\rceil$" to "$\lfloor x\rfloor$and$\lceil x\rceil$" page 75, line 6 white out the little dot to the left of the \sum sign page 83, new graffito for the margin (just below (3.23)) "Notice that$x\mathbin{\rm mumble}y=(-x)\mathbin{\rm mod}y$." *page 88, new sentence to follow line 5 We can assume without loss of generality that$0<\alpha<1$. *page 88, lines 12 and 13 change "Without ... let us" to "Let us" page 105, line 4 from the bottom change "others that have ... more divisors" to "others that have nontrivial divisors" page 106, line 4 from the bottom change "This contradiction" to "Hence$p_1$must be either$q_2$or$\cdots$or$q_n$; yet$p_1$is strictly smaller! This contradiction" page 108, lines 5--7 change "This contradicts ... infinitely many." to "Every finite set of prime numbers must therefore be incomplete." page 108, line 6 from the bottom change "smallest factor" to "smallest prime factor" page 112, line 12 change "and its" to "and$k=n$, while it has its" page 112, bottom line change "powers-of-2" to "powers-of-$2$" page 119, line 20 change "$0\le b<a<n$" to "$0\le b<a\le n$" *page 120, line 8 change "following S" to "following f(S)" page 130, line 5 from the bottom change "with the possible exception of" to "including" page 136, lines 4, 5, 6, 11 from the bottom use larger parentheses around the displayed fractions page 144, line 4 from the bottom change "all solutions" to "all relevant solutions" page 147, line 2 of exercise 37 change "log" to "ln" page 147, line 1 of exercise 38 change$a>b$to$a>b>0$page 162, bottom line change "and we" to "unless$r$is a nonnegative integer, and we" page 169, generalization of identity (5.26) change "$\sum_{0\le k\le l}$" to "$\sum_{-q\le k\le l}$"; the conditions are now "integers$m,n\ge0$, integer$l+q\ge0$." page 171, line 7 change "integers m,n\ge0" to "integers m,n" page 180, line 20 change "using (5.7)" to "using (5.6) and (5.7)" page 182, line 7 change (5.6) to (5.5) page 184, line 5 change "between 0" to "between$0$" page 206, line 6 change "using (5.56)" to "using (5.13) and (5.14)" page 206, line 8 from the bottom change "form a field" to "with$-\infty<n<\infty$form a field" page 221, line 17 change "$D^k F(k)$" to "$D^k F(z)$" page 229, line 2 from the bottom change "383" to "384" *page 230, line 10 change "summable." to "summable, using ideas pioneered by Sister Celine Fasenmyer in the 1940s ." page 231, line 8 change "$q$and" to "$q$, and" (twice) page 233, line 12 from the bottom change "$\beta_0$, \dots\$\beta_l$" to "$\beta_0$, \dots,$\beta_l$" *page 239, line 7 from the bottom change "$k$; see exercise 107." to "$k$." page 243, line 1 change " Which" to "Which" page 245, bottom line change "binomial number system" to "combinatorial number system" page 246, replacement for the second line of exercise 42$\sum_{k=0}^m (-1)^k/{n\choose k}$in closed form when$0\le m\le n$. *page 247, top line change "$\sum_{k\le n}$" to "$\sum_{k=0}^n$" page 248, top line change "Use" to "Given$n$and$z$, use" *page 253, line 4 from the bottom change "constant$\alpha$" to "constant$\alpha\ne0$" page 254, line 8 change " What" to "What" page 268, displayed equation (6.34) change "0;" to "0." page 273, just below the illustration change "we require the edges of the cards" to "we assume that card$k$rests on card$k+1$, for$1≤k<n$. We also require the right edge of each card" page 276, line 16 change "if n is in" to "if 1/n is in" page 288, graffito change "Johann" to "(Johann"; also change "1635" to "1631" page 292, line 19 from the bottom change "Édouard" to "Edouard" page 295, new graffito to be placed near (6.113) [The anonymous author of a classic Sanskrit work, Prākṛta Paiṅgala (c. 1320), actually knew this representation many centuries ago.] *page 299, line 2 from the bottom change "Leonhard Euler  in 1765" to "Daniel Bernoulli in 1728" page 302, line 17 change "Euler observed" to "Euler  observed" page 312, last line of exercise 31 change ".)." to ".)" page 332, equation (7.15) squeeze things together so that the period doesn't overlap the equation number page 338, line 2 from the bottom change "for$z$" to "for$z$and multiplying by$a$" page 358, line 6 from the bottom change "$a_2\ldots$" to "$a_2,\ldots$" page 360, line 4 change "$k\ge0$" to "k>0" page 361, lines 8 and 9 change "call this a Fuss-Catalan number" to "call it the Fuss--Catalan number" page 373, line 8 change "$\cdots n$" to "$\cdots+n$" below the summation sign page 385, line 12 change "that X can assume" to "for which Pr(X<x) is nonzero" page 385, lines 12 and 15 chance "all$x$" to "all$x\in X(\Omega)$" page 386, line 6 from the bottom change "random dice" to "fair dice" *page 417, lines 7 and 8 from the bottom insert a plus sign at the beginning of each line page 437, line 10 change "$(X,Z)$and" to "$(X,Z)$, and" page 440, line 12 from the bottom change "growth ratios" to "rates of growth" page 442, line 12 change "is constant" to "is a nonzero constant" page 442, line 2 from the bottom change "is in" to "are in" page 443, graffito change "... wir" to "..., wenn wir"; also replace the uses of German sharp-s by "ss" (twice) page 444, line 20 change "de Bruijn's L(n)'" to "the quantity L(n) above" page 445, addition to the graffito "-- Michael Stueben" page 449, line 12 from the bottom change "base-10" to "base-$10$" page 457, line 12 change$\pi(n)$to$\pi(p)$page 457, bottom line change$\pi(n)$to$\pi(p)$*page 463, line 3 from the bottom change$O(n)$to$n\ln\ln n + O(n)$page 500, in answer 1.21 change m to q (twice), and "an m" to "a q" page 501, line 2 of answer 1.26 change m to q page 502, line 7 change "doesn't hold" to "doesn't apply" page 503, line 11 change "$...n!$=$S_{n-1}...$" to "$...n! = S_{n-1}...$" page 508, line 7 from the bottom change$n>0$to$n\ge0$*page 512, lines 11 and 12 from the bottom change "a segment of length$2k$" to "a segment of length$2k-1$"; also change "a segment of length$2k-2$" to "the interior of a segment of length$2k$" page 516, line 2 from the bottom change "20000" to "49081" page 518, line 2 from the bottom change "$S(3),\ldots,\rangle$" to "$S(3)\ldats\,\rangle"$*page 519, lines 4 and 5 from the bottom change$m_2<n_2$to$m_2\le n_2$(twice) *page 520, line 10 change "90%" to "80%" *page 522, line 4 change "1300" to "13000" *page 522, line 11 add the qualification "integer$m\ge2$," *page 522, line 13 change "\lfloor n/m\rfloor" to "4\lfloor n/m\rfloor + [n mod m=m-1] - [n mod m=0]" page 522, in exercise 56 change "stated product" to "stated fraction" (twice) *page 523, line 11 from the bottom change "cp^\theta" to "p^\theta" (twice) *page 524, line 9 change "divisor d" to "divisor d>2" page 530, replacement for the 4th line of answer 42 $$\sum_{k=0}^m(-1)^k/{n\choose k}=(-1)^{x-1}{n+1\over n+2}\Big/{n+1\choose x}\Bigr\vert_0^{m+1}={n+1\over n+2}+\Bigl({m+1\over n+2}\Bigr){(-1)^m/{n\choose m}}.$$ *page 535, lines 4 and 5 of answer 5.69 change "n" to "m" in two places where n occurs by itself *page 536, replacement for lines 5--7$m(m-n)\ldots(m-(k-1)n)$at least$r$times if$p^r$divides$k!$, because we have$m(m-n)\ldots(m-(k-1)n)\equiv n^k(mn')^{\underline k}= k!\,n^k{mn'\choose k}\equiv0$(mod$p^r$) when$nn'\equiv1$. *page 537, lines 2 and 3 from the bottom the left-hand side of the first equation should be simply$zt{\cal B}_t(z)^{-1}{\cal B}'_t+1$, and the second equation should be corrected in the analogous way *page 537, line 2 from the bottom replace$\cal E$by${\cal E}_t$in right-hand side of this equation *page 540, answer 5.94 change$k$to$k-1$page 550, line 6 change "104.607361" to "104.60736" *page 550, line 2 from the bottom change "a and b odd" to "b odd" page 551, new graffito near answer 6.24 (Of course Euler knew the Genocchi numbers long before Genocchi was born; see , Volume 2, Chapter 7, §181.) *page 554, line 16 from the bottom change$H_r+\sum$to$H_r-\sum$*page 555, new display replacing line 7 S_m(p)=\sum_{k=0}^{p-1}\sum_{j=0}^m{m\brace j}k^{\underline j} = \sum_{j=0}^m{m\brace j}{p^{\underline{j+1}}\over j+1} \equiv 0. page 559, answers 74 and 75 [I'm changing the notation for Euler numbers to agree with papers in combinatorics instead of papers in numerical analysis: Now$T_n(1)=2^nE_n$for all$n\ge0$.] *page 564, comment regarding answer 6.91 An elegant solution to this research problem has been found by Philippe Flajolet and Helmut Prodinger, SIAM Journal on Discrete Mathematics 12 (1999), 155--159. page 564, improvement to answer 6.94 change "has the form ... where" to "equals$\sum_k(wF(\alpha'+\beta'+ \gamma',\alpha'+\beta',\alpha')+zF(\alpha+\gamma,\alpha+\beta,\alpha))^k(1)$, where" page 564, line 6 from the bottom change "382" to "383" page 564, new answer for exercise 6.95 An elegant solution to this research problem was found by Manuel Kauers, Journal of Symbolic Computation 42 (2007), 948--970. page 568, line 11 from the bottom make the third ")" larger page 569, line 8 delete the first "(" on this line page 570, line 2 from the bottom change "$A_n=\vert E_n\vert+T_n$is a" to "$A_n$is the Euler number$E_n$of exercise 6.74, namely a" page 571, line 2 from the bottom insert a plus sign after$2/p^4$page 575, answer to research problem 7.57 change "currently offers$500 for a solution" to "repeatedly offered $500 for a solution to this problem" page 576, line 15 from the bottom change "G(y)" to "G(Y)" *page 580, line 9 change "$S_A(A:B)+S_B(B:C)$" to "$S_A(A:C)+S_B(B:C)$" page 585, line 10 from the bottom change "p_{mn}" to "p_{m,n}" *page 590, line 12 from the bottom change "p\perp q. And (p+1)\divides" to "pq>0 and p+q=" *page 599, line 8 change "$O(k^3m^{-2}\log n)$" to "$O(k^3m^{-2}\log n)+O(m^{-1})$" page 600, line 14 from the bottom change "($a$)" to "(a)" page 604, reference 3 add new sentence: "[See also P. E. Böhmer, Über die Transzendenz gewisser dyadischer Brüche,'' Mathematische Annalen 96 (1927), 367--377, 735.]" page 605, in reference 16 change "[See also ... 246.]" to "[This triangle was first found by L. Seidel, Ueber eine einfache Entstehungsweise der Bernoulli'schen Zahlen und einiger verwandten Reihen,'' Sitzungsberichte der mathematisch-physikalischen Classe der königlich bayerischen Akademie der Wissenschaften zu München 7 (1877), 157--187.] page 605, marginal notes for references 15 and 16 interchange these;  is cited on page 633 and  on page 635. page 607, reference 40 change "6 (1860)" to "3 (1861) page 607, reference 49 insert closing quotes before Portugaliae page 608, references 57 and 58 (I should have transcribed the titles using the 19th-century Russian orthography of the original publications) page 609, lines 3 and 4 of reference 77 change "math- ematische" to "ma- thematische" page 610, reference 87 change "25 May 1902" to "15 November 1896, 25 May 1902," page 611, marginal note for reference 103 change "278." to "277, 278." page 613, reference 119 change "Faulhabern" to "Faulhaber" page 613, reference 122 change "Leonardo Fibonacci [Pisano]" to "Leonardo filio Bonacci Pisano [Fibonacci]" page 615, reference 149 add closing double-quotes after the comma before Messenger page 617, reference 176 change "its Applications" to "Its Applications" page 617, reference 180 change "(1944)" to "(1945)" page 618, reference 193 change "Structures and" to "Structures &" page 620, marginal note for reference 220 change "267." to "267, 598." page 621, reference 235, add a new sentence [More general formulas had been published by L. Toscano, Commentationes 3 (Vatican City: Accademia della Scienze, 1939), 721--757, Equations 17 and 117.] page 622, reference 249 change "Zhaī" to "Zhāi" page 623, reference 263 change "Maclaurin" to "MacLaurin" page 628, reference 331 change "" to "ee"; also change "its Applications" to "Its Applications" page 628, a new reference 336' Tor B. Staver, Om summasjon av potenser av binomiaalkoeffisientene,'' Norst Matematisk Tidsskrift 29 (1947), 97--103. [Cited on page 634.] page 630, last line of Venn's citation (reference 359) change "9" to "10" page 630, a new reference 361' J. Wasteels, Quelques propriétés des nombres de Fibonacci,'' Mathesis, series 3, 11 (1902), 60--62. [Cited on page 635.] *page 631, new entry for bibliography (cited on page 230) 382 Doron Zeilberger, Sister Celine's technique and its generalizations,'' Journal of Mathematical Analysis and Applications 85 (1982), 114--145. See also Sister Mary Celine Fasenmyer, `A note on pure recurrence relations,'' American Mathematical Monthly 56 (1949), 14--17. [Also renumber the former entries 382 and 383, which now become 383 and 384.] page 633, right column entry for 3.53 change ".*." to ".*" page 634, left column, entry for 5.38 change "1.2.6--16" to "1.2.6--56" page 634, right column, new entry 5.100 Staver [336']. page 635, left column, replacement entry 6.44 Wasteels [361']. page 637, upper right corner in some printings the spurious word "INDEX" appeared here page 637, left column, entry for$\Phi$change "137--139" to "138--139" page 637, right column, entry for$\sim\$
change "428--429" to "110, 439--443, 448--449"
page 638, left column, under algorithms, Euclid's
change "103" to "103--104"
page 638, left column, under algorithms, Gosper-Zeilberger
change "255" to "255, 319, 547"
page 638, left column, entry for Alice
change "430" to "427, 430"
page 638, right column, entry for baseball
change "648" to "622, 638"
page 638, right column
change "Bernoulli, Daniel Julius" to "Bernoulli, Daniel"
page 639, left column, entry for Bernoulli numbers
denominators of, 315, 551, 574; numerators of, 555
page 639, left column, entry for Bill
change "430" to "427, 430"
page 639, left column, entry for binary logarithm
change "70" to "70, 449"
page 639, right column
delete "binomial number system, 245"
page 639, right column, new entry
"Böhmer, Paul Eugen, 604"
page 640, left column, under cards, stacking
change "280" to "278"
page 640, right column, entry for closed form
change "321" to "321, 331"
page 640, right column, new entry
"combinatorial number system, 245"
page 641, left column, entry for computer algebra
change "268" to "254"
page 641, left column, entry for convergence
of power series, 206, 331--332, 348, 451, 532
page 641, right column, entry for Coxeter
change "Macdonald" to "MacDonald"
page 641, right column, entry for cyclic shift
change "362" to "359, 362"
page 641, right column, entry for deg
change "226" to "227"
page 641, right column, entry for derangements
derangements, 194--196, 250
page 642, right column, entry for Doyle
change "Arthur Conan" to "Arthur Ignatius Conan"
page 643, left column
add page 551 under Euler, Leonhard
page 643, left column, entry for Euler's constant
change "319" to "316, 319"
page 643, right column, entry for F
change "hypergeometric functions" to "hypergeometric series"
pge 643, right column, entry for fair dice
change "417" to "392, 417, 429"
page 644, left column, new entry
"Fasenmyer, Mary Celine, 230, 631"
page 644, left column, under Fibonacci, addition
change "317" to "318"
page 644, right column, entry for fractions, unit
change "95" to "95, 101"
page 645, left column, entry for games
change "Penny" to "Penney"
page 645, left column, Gauss entry
change "Johann Friedrich" to "Johann Friderich"
page 645, right column, under Gosper algorithm, examples
change "534" to "530, 534"
page 645, right column, under graphs of functions, 1/x
change "262--263" to "276--277"
page 645, right column, under graphs of functions, partial sums of a sequence
change "345--346" to "359--360"
page 646, left column
change "Håland" to "Håland Knutson"
page 646, right column, under hypergeometric series, partial sums of
change "230, 224" to "230"
page 647, right column, new entry
"Kauers, Manuel, 564"
page 648, left column, Lekkerkerker entry
change "Cornelius" to "Cornelis"
page 648, left column, entry for lg
change "70" to "70, 449"
page 648, left column, Li Shan-Lan entry
change "Rénshū (=" to "(= Rénshū ="
page 648, left column, entry for ln
change "276" to "276, 449"
page 648, left column
change "Loú Shìtūo" to "Lóu, Shìtuó"
page 648, right column
change "Maclaurin" to "Maclaurin (= Mac Laurin)"
page 649, left column, entry for natural logarithm
change "276" to "276, 449"
page 649, under number system
change "binomial" to "combinatorial"
page 650, right column, under permutations, excedances in
change "314" to "316"
page 650, right column, under permutations, fixed points in
change "418" to "428"
page 650, right column, under permutations, left-to-right maxima in
change "314" to "316"
page 650, right column, under Pfaff, reflection law
change "247" to "244, 247"
page 650, right column, under phi, in solutions to recurrences
change "285--286" to "299--301"
page 650, right column, entry for pi
change "3.14159" to "3.14159)"
page 650, right column, entry for Phi function
change "137--139" to "138--139"
page 650, right column, entry for Pisano
Pisano, Leonardo filio Bonacii, 613, see Fibonacci
page 651, left column, under prime numbers, Mersenne
change "522" to "522--523"
page 651, right column, entry for probability distributions
change "367" to "381"
page 651, right column, entry for probability distributions, uniform
change "420--421" to "418--421"
page 651, right column, entry for Rahman
change "Mizanur" to "Mizan"
page 652, left column, entry for recurrences, implicit
change "136--138, 193--194" to "136--139, 193--195"
page 652, left column, new entry
regular expressions, 278
page 652, right column, entry for Saalschütz
change "627, 634" to "627"
page 653, left column
Seidel, Philipp Ludwig von, 605
page 653, left column, entry for Sierpiński
change "Wacław" to "Wacław Franciszek"
page 653, right column, new entry
Staver, Tor Bøhm, 628, 634
page 654, left column, new entry
Stueben, Michael, 445
page 655, left column, entry for tail of a sum
change "452--455" to "466--469, 488--489, 492"
page 655, left column, entry for tangent numbers
change "620" to "570, 620"
page 655, right column, entry for trivial
change "129" to "105, 129"
page 655, left column, new entry
Toscano, Letterio, 621
page 655, right column, entry for uniform distribution
change "418--419" to "418--421"
page 656, left column, new entry
Wasteels, Joseph, 630, 635
page 656, right column, second entry for Yao
change "Foong Frances" to "Frances Foong Chu"
page 656, right column, third entry for Yao
change "Yaó" to "Yáo"
back cover, line 1 at the top right
change "Graham ," to "Graham,"

A dozen or so entries in the bibliography have been updated to refer to items that have been reprinted in the author's Selected Papers. As a result, several bibliographic entries now appear on different pages than they used to.

One reader has also pointed out that the formulas in this book mix two slightly different styles of commas. All commas should actually have the same style as the "concrete roman" commas in the text. ### Don Knuth's other books  