Concrete Mathematics, Second Edition

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

Chinese translation by Lai FeiPei, Ju Ti Shu Xue (Taipei: Dong Hua Publishing Co., 1990), xv+731pp.
Chinese translation by Chen YanWen, Ju Ti Shu Xue (Taipei: Ru Lin Publishing Co., 1991), xii+695pp.
Chinese translation by Xingu Zhuang, Ju Ti Shu Xue (Xi'an: Xi An Dian Zi Ke Ji Da Xue Chu Ban She, 1992), xii+539pp.
Chinese translation by somebody (Beijing: China Machine Press), in preparation.
Italian translation edited by Giovanni Monegato, Matematica Discreta (Milan: Editore Ulrico Hoepli, 1992), xviii+607pp.
Japanese translation by Makoto Arisawa, Michiaki Yasumura, Tatsuya Hagino, and Kiyoshi Ishihata, Kompyuta no Suugaku (Tokyo: Kyoritsu-Shuppan, 1993), xvi+606pp.
Portuguese translation by Valéria de Magalhães Iorio, Matemática Concreta (Rio de Janeiro: Livros Técnicos e Cientíicos Editora, 1995), xii+477pp.
Russian translation by A. B. Khodulev and B. B. Pokhodzei, with foreword by V. Arnol'd, Konkretnaya matematika (Moscow: Mir, 1999), 704pp.
Polish translation by P. Chrzastowski, A. Czumaj, L. Gasieniec, and M. Raczunac, Matematyka Konkretna (Warszawa: Polskie Wydawnictwa Naukowe, 1996), 718pp.
Hungarian translation by S. Fridli, J. Gonda, A. Kovács, L. Lakatos, and Cs. Láng, Konkrét matematika (Budapest: Műszaki Könyvkiadó, 1998), xvi+647pp.
Spanish translation (Addison-Wesley Spain and Universidad Autonoma de Madrid), in preparation.
French translation by Alain Denise, Mathématiques concrètes (Paris: International Thomson Publishing, 1998), xiv+688pp.; now distributed by Éditions Vuibert.
Croatian translation (Zagreb: Golden Marketing), in preparation.
Greek translation (Athens: Klidarithmos), in preparation.

Introduction to the mathematics that supports advanced computer programming and the analysis of algorithms. An indispensable text and reference not only for computer scientists --- the authors themselves rely heavily upon it --- but for serious users of mathematics in virtually every discipline. Based on the course Concrete Mathematics taught by Knuth at Stanford University from 1970--1989. The second edition includes important new material about the revolutionary Gosper-Zeilberger algorithm for mechanical summation. Complete answers are provided for more than 500 exercises.

It is to be hoped that this book succeeds in convincing many educators, not only in computer science but also in mathematics, that courses like this pay off! -- J. H. Van Lint, International Reviews on Education (1990)
It is always a pleasure to look again into this book full of carefully explained and enthusiastically presented mathematics. -- Volker Strehl, Mathematical Reviews (1997)

Major topics include

Available from the publisher, Addison-Wesley Publishing Company.

Errata

For a list of corrections to known errors in the pre-1998 printings of the second edition, you may download the 1994--1997 errata file in compressed PostScript format (74K bytes). This file was generated by the TeX file errata97.tex in directory ftp.cs.stanford.edu:pub/concretemath.errata.old using special macros and fonts found in that directory. Errata lists for various printings of the first edition can also be found there.

Here is a list of all nits that have been picked so far in the 1998 printing. (Most of these have been corrected in the 20th printing, December 2006.) An asterisk (*) marks significant 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 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 "be the basic" to "be sets that correspond to the basic"
page 41, line 2 from the bottom
change "at least seven" to "at least eight"
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 65, exercise 31
change " Riemann's" to "Riemann's"
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 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 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 1 of exercise 38
change $a>b$ to $a>b>0$
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 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 [382]."
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 274, line 2
page 288, graffito
change "Johann" to "(Johann"; also change "1635" to "1631"
page 292, line 19 from the bottom
change "Édouard" to "Edouard"
*page 299, line -2
change "Leonhard Euler [113] in 1765" to "Daniel Bernoulli in 1728"
page 302, line 17
change "Euler observed" to "Euler [112] 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 373, line 8
change "$\cdots n$" to "$\cdots+n$" below the summation sign
*page 417, lines -7 and -8
insert a plus sign at the beginning of each line
page 437, line 10
change "$(X,Z)$ and" to "$(X,Z)$, and"
page 442, line 12
change "is constant" to "is a nonzero constant"
page 442, line -2
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 449, line 12 from the bottom
change "base-10" to "base-$10$"
*page 463, line 3 from the bottom
change $O(n)$ to $n\ln\ln n + O(n)$
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 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 523, line -11
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 line 6
$j$ of the factors $m(m-n)\ldots(m-(p^r-1)n)$ are multiples of $p^{r-j}$ for all $r\ge j\ge 1$ and all $m$.
*page 537, lines 2 and 3 from the bottom
the left-hand side of the first equation should be simply $zt{\cal B}_t^{-1}(z){\cal B}'_t+1$, and the second equation should be corrected in the analogous way
*page 540, answer 5.94
change $k$ to $k-1$
page 550, line 6
change "104.607361" to "104.60736"
*page 550, line -2
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 [110], 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
make the third ")" larger
page 569, line 8
delete the first "(" on this line
page 570, line -2
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 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
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
change "p_{mn}" to "p_{m,n}"
*page 590, line -12
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
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.]"
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; [15] is cited on page 633 and [16] 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 623, reference 263
change "Maclaurin" to "MacLaurin"
page 628, reference 331
change "eë" to "ee"; also change "its Applications" to "Its Applications"
*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 637, upper right corner
in some printings the spurious word "INDEX" appeared here
page 639, left column, entry for Bernoulli numbers
denominators of, 315, 551, 574; numerators of, 555
page 639, right column
delete "binomial number system, 245"
page 639, right column
new entry "Böhmer, Paul Eugen, 604"
page 640, right column
new entry "combinatorial number system, 245"
page 641, left column, entry for convergence
of power series, 206, 331--332, 348, 451, 532
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 644, left column
new entry "Fasenmyer, Mary Celine, 230, 631"
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 646, left column
change "Håland" to "Håland Knutson"
page 647, right column
new entry "Kauers, Manuel, 564"
page 648, left column, Lekkerkerker entry
change "Cornelius" to "Cornelis"
page 648, right column
change "Maclaurin" to "Maclaurin (= Mac Laurin)"
page 650, right column, entries for permutations
change "314" to "316"
page 650, right column, entry for pi
change "3.14159" to "3.14159)"
page 650, right column, entry for Pisano
Pisano, Leonardo filio Bonacii, 613, see Fibonacci
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 655, left column, entry for tail of a sum
change "452--455" to "466--469, 488--489, 492
page 655, right column, entry for trivial
change "129" to "105, 129"
page 655, left column, new entry
Toscano, Letterio, 621.
page 656, right column, second entry for Yao
change "Foong Frances" to "Frances Foong Chu"

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.

With these corrections, the authors hope that the book is now error-free. But (sigh) it probably isn't. Therefore Knuth will gratefully deposit 0x$1.00 ($2.56) to the account of the first person who finds and reports anything that remains technically, historically, typographically, or politically incorrect. Please send suggested corrections to knuth-bug@cs.stanford.edu, or send snail mail to

Prof. D. Knuth
Computer Science Department
Gates Building 4B
Stanford University
Stanford, CA 94305-9045 USA.

DO NOT SEND EMAIL TO KNUTH-BUG EXCEPT TO REPORT ERRORS IN BOOKS! And if you do report an error via email, please do not include attachments of any kind; your message should be readable on brand-X operating systems for all values of X.

SPECIAL NOTE TO THE SPEAKERS OF FRENCH AND OTHER EXOTIC LANGUAGES: Numerous quotations and bibliographic citations found in this book have been copied verbatim from the original sources. If you believe you have found a typographic error, you must prove it by showing that the original was incorrectly transcribed; believe it or not, your language has changed over the years, just as English has.

Sample exams

Midterm and final exams from the last two times Knuth taught this course at Stanford (1988 and 1989) are now available, together with the answers, as compressed PostScript files. The teaching assistants who helped to prepare these exams were Sheralyn Listgarten and Sridhar Raman (1988); Alan Hu and Robert Kennedy (1989).

Ron Graham's home page

Don Knuth's home page

Oren Patashnik's home page

Don Knuth's other books

Valid HTML 4.01 Transitional