![]() |
|
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 of the second edition by Zhang Mingyao and Zhang Fan,
Ju Ti Shu Xue -- Ji Suan Ji Ke Xue Ji Chu (Beijing:
Turing Books, 2013),
xii+564pp.
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.
Japanese translation of the second edition by Makoto Arisawa, Michiaki
Yasumura, Tatsuya Hagino, and Kiyoshi Ishihata,
Kompyuta no Suugaku
(Tokyo: Kyoritsu-Shuppan, 2020), xvi+624pp.
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, Конкретная математика
(Moscow: Mir, 1999), 703pp.; see also
(Moscow: Binom, 2009).
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 Autónoma 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.
Greek translation by Christos A. Kapoutsis (Athens:
Klidarithmos, 2011), 640pp.
Korean translation by Ryu Gwang, 구체 수학 (Seoul:
Insight
Press, 2018), 816pp.
Croatian translation (Zagreb: Golden Marketing), in preparation.
Macedonian translation (Skopje:
Ars Lamina), 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)
Although designed as a textbook, the book is also a valuable reference, and is loaded with useful results, especially in the exercises (all of which are solved in the back of the book). This is my go-to book for any problem dealing with binomial coefficients, Fibonacci numbers, harmonic numbers, or evaluation of finite sums. -- Allen Stenger, MAA Reviews (2010)
This is one of those books you keep forever, purely for its utility. -- Naomi Novik, review on amazon.com (2010)
Major topics include
Available from the publisher, Addison-Wesley Publishing Company.
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. See also the list of errors corrected between January 1998 and May 2013, which is in HTML format.
And here is a list of all nits that have been picked so far since the 27th printing (May 2013), not counting the important replacement pages for the changes in the 34th printing (January 2022) because of a correction to the definition of Bernoulli numbers. An asterisk (*) marks significant technical errors that are not merely typographical:
- page xi, line 3
- change "Stirling subset number" to "Stirling partition number"
- page 1, line 2 before the illustration
- change 'Edouard' to 'Édouard'
- page 8, line 8
- change 'only two regions per line' to 'only two regions per bent line'
- page 17, line 1 of exercise 2
- change 'the shortest sequence of moves that transfers' to 'the minimum number of moves that can transfer'
- page 28, line 4
- change "quicksort" to "quicksort [209, Algorithm 5.2.2Q]"
- *page 30, lines 8, 11, 17, and 25
- change 'associative law' to 'pairing law'
- *page 31, line 8 from the bottom
- change 'associative' to 'pairing'
- *page 33, line 11
- change 'associative law' to 'pairing law'
- *page 34, line 2 from the bottom
- change 'associative law' to 'pairing law'
- *page 41, line 3
- change 'associative law' to 'pairing law'
- *page 60, line 8 from the bottom
- change 'associative' to 'pairing'
- *page 61, line 3
- change 'associative law' to 'pairing law'
- *page 63, line 4 of exercise 11
- change 'associative' to 'pairing'
- *page 64, line 4 of exercise 25
- change 'associative' to 'pairing'
- page 75, line 8
- use a bigger [ before $m\in$ and a bigger ] after $/k)$
- page 77, line 2
- change 'a real number' to 'a positive real number'
- page 87, display on lines 8--10
- change '$k<n$' to '$k<a^2$' under the first $\sum$; and append ', integer $a$' at the end of the formula.
- *page 101, line 1 of exercise 52
- change 'nonnegative real numbers $\alpha$ and $\beta$' to 'real numbers $\alpha$ and $\beta$ with $\alpha>0$ and $\alpha+\beta>0$'
- *page 101, line 6 of exercise 52
- change 'rational' to 'distinct'
- *page 101, last line of exercise 52
- change '$2^{k-1}$' to '$2^{m-k}$'
- page 106, line 4 from the bottom
- change 'or $q_n$' to 'or $q_k$'
- pages 107 (bottom) and 108 (top)
- change 'Suppose there were only finitely many ... None of the' to: 'Consider any finite set of primes, say $\{P_1,P_2,\ldots,P_k\}$. Then, said Euclid, we should think about the number
$$M=P_1\cdot P_2\cdot\ldots\cdot P_k+1.$$
None of the'- page 108, line 7 (in the 27th printing only)
- change 'primes numbers' to 'prime numbers'
- page 108, a new graffito
- "Oh, I see: The formula $e_1e_2\ldots e_{n-1}$ means $\prod_{k=1}^{n-1}e_k$, so it is equal to $1$ (an empty product) when $n=1$."
- page 109, line 13
- change '1984' to '1985'
- page 114, line 11
- change "progression:" to "progressions: When $n>0$ we have"
- page 128, line 12 from the bottom
- change "page 274" to "page 290"
- page 151, line 15 (the sequence for script-P sub 5)
- change the second occurrence of 2/5 to 3/5
- page 167, line 10 (the displayed formula)
- change "integer $m\ge0$" to "integer $m$"
- page 174, line 4 from the bottom
- change "apply (5.7)" to "apply (5.3) or (5.7)"
- page 178, line 10 from the bottom (the displayed formula)
- change $m\ge0$ to $m\ge1$
- page 178, line 4 from the bottom (the displayed table)
- delete the entry for $m=0$
- page 179, line 9 from the bottom
- change $m\ge6$ to $m\ge7$
- page 192, lines 2 and 3 from the bottom
- change 'rule (5.45)' to 'rule (5.44)', and change 'way:' to 'way using (5.40):'
- page 201, add new graffito in bottom half of page:
- News flash: $\ln\Bscr_t(z)=\sum_{k\ge1}{tk\choose k}z^k/(tk)$; $\ln\Escr_t(z)=\sum_{k\ge1}(tk)^{k-1}z^k/k!$.
- page 213, lines 6, 7, and 8
- replace these lines by: general sum $\sum_{k\le n}{n-k\choose k}z^k$ considered in (5.74); and that sum leads, for example, to a closed-form expression for $$F\Biggl({n+1,-n\over 1/2}\Biggm|{-z\over4}\Biggr) = \sum_{k\ge0}{n+k\choose n-k}z^k = \sum_{k\le n}{2n-k\choose k}z^{n-k}.$$
- page 214, line 10
- change "integer n\ge0.$$ When" to "integer n\ge0,$$ if we replace $(a,b,c,k)$, respectively by $(a+n-1,b+n-1,n,k-n)$. When"
- page 214, bottom (in the 36th printing only!)
- the following two lines were omitted by mistake: "Our hard-won identity in Problem 9 of Section 5.2 reduces to $${1\over1+x}\hyp{x+1,\,n+1,\,-n\,}{1,\,x+2}1=(-1)^nx\_n\,x\_{-n-1}\,. $$"
- page 220, line 3
- remove spurious comma at the end of this line
- page 258, line 1
- change "subsets" to "set partitions"
- page 260, lines 17 and 19
- change "subset numbers" to "partition numbers"
- page 261, line 17
- change "Stirling subset numbers" to "Stirling partition numbers"
- page 262, line 2 from the bottom
- change "Stirling subset numbers" to "Stirling partition numbers"
- pages 275 (bottom) and 276 (top)
- change $\sum_k 1/k$ to $\sum_{k>0}1/k$
- *page 280, line 2
- change "(6.99)" to "(6.99), with $(m,k,j)$ replaced by $(n-1,m,k-1)$,"
- page 283, and 43 other pages!
- see the replacement pages mentioned above
- page 287, line 3
- change $\sum_{n\ge0}$ to $\sum_{n\ge1}$
- page 288, line 4
- change 'sum of $n$th powers' to 'sum of $m$th powers'
- page 305, line 14
- omit '(This is "Halphen's theorem" [174].)'
- page 306, line 1
- change 'Thus' to 'Thus—as implicitly observed by Halphen [174]—'
- page 317, last line of exercise 76
- change '$n$ is even' to '$n>0$ is even'
- page 373, line 6
- change $P(z)$ to $\widehat P(z)$
- page 376, in exercise 32
- enclose the sets of arithmetic progressions within braces (three times); for example, the second instance is $\bigl\{\{2n\}, \{4n+1\}, \{4n+3\}\bigr\}$
- page 428, line 9
- enclose $\alpha^{\alpha n}(1-\alpha)^{(1-\alpha)n}$ in parentheses
- page 429, exercise 8.22
- change "law of conditional expectations and variances" to "law of total variance"
- page 450, equation (9.27)
- add the qualification ", if $f(n)$ is never zero"
- page 469, the graffito
- append "-- Stuart McLean"
- page 477, line 10
- change $R_4(n)$ to $R_4(n)+O(n^{-5})$
- page 481, lines 8, 9, 10 from the bottom
- change "(The value ... constant exists.)" to: "(Stirling's original formula was actually a bit different; (9.91) is de Moivre's modification [76]. Stirling [343, p. 137] stated without proof that $e^\sigma=\sqrt{2\pi}$; we aren't quite ready to prove that fact.)"
- page 481, bottom line
- change 'approximated' to 'approximated via Euler's formula'
- page 488, bottom line
- change $k>n^{1/2+\epsilon$ to $\vert k\vert>n^{1/2+\epsilon$
- page 490, lines 1 and 2 of exercise 21
- change $O(\log n)^{-2}$ to $O(\bigl((\log n)^{-2}\bigr)$ and $O(\log n)^{-3}$ to $O(\bigl((\log n)^{-3}\bigr)$
- page 504, last line of answer 2.25
- change $\sum_{k\in K}1=\#K$ to $\sum_{k\in K}c=c\#K$
- page 514, line 4 from the bottom
- change ‘irrational’ to ‘a repeated’
- *page 514, bottom line and top of page 515
- change 'rational examples' to 'examples with distinct $\alpha$'s'
- page 517, line 1
- change $\rho(2k+1)$ to $\rho(2k-1)$
- page 525, new copy for answer 4.67
- M. Szegedy proved this conjecture for all large n; then R. Balasubramanian and K. Soundararajan found a complete solution. See [95, pp. 78–79], [348], [55], and [19'].
- page 525, new graffito for answer 4.69
- Late-breaking news: The $10,000 prize has been won! See Kevin Ford, Ben Green, Sergei Konyagin, James Maynard, and Terence Tao, Journal of the American Mathematical Society, vol. 31 (2018), pages 65–105.
- *page 533, in answer 5.55
- change $(k+B_N)$ to $(k+B_N)(k+1)$; change $P(k)Q(k-1)/P(k-1)R(k)$ to $P(k+1)Q(k)/P(k)R(k+1)$; and change "polynomial" to "polynomial in $k$"
- page 549, new graffito for answer 5.114
- Late-breaking news: W. Zudilin has found an explicit expression for each $c_n^{(m)}$ as a summation of binomial coefficients; see Electronic Journal of Combinatorics, vol. 11 (2004), #R22, pages 1–8.
- page 552, new answer 6.32
- $\sum_{0\le k\le m}k{n+k\brace k}={m+n+1\brace k}-{n\brace-1}= {m+n+1\brace k}-[n=-1]$ generalizes (6.22) to negative $n$; and $\sum_{k\le n}{k\brace m}(m+1)^{n-k}={n+1\brace m+1}$ generalizes (6.20) to negative $m$, $n$.
- *page 553, line 3 of answer 6.44
- change $(m-k,m)$ to $(k,m-k)$
- *page 568, line 1 of answer 7.24
- change $n\sum$ to $n\sum_{m>0}\sum$
- page 577, line 4 of answer 8.19
- change "when $a,b\ge0$" to "when $X_1$ and $X_2$ are independent"
- page 580, replacement for lines 2 and 3 of answer 8.31
- $A=1$; $B=\half zA+\half zC$; $C=\half zB+\half zD$; $D=\half zC+\half zE$; $E=\half zD+\half zA$. (And the following lines are revised to fit this better approach.)
- page 580, line 3 from the bottom
- change $1/x^{98}(4-2x-x^2)$ to $1/(x^{98}(4-2x-x^2))$
- page 593, in answer 9.19
- change 2.928968256 to 2.928968258 and 3628712.4 to 3628800.05
- page 604, marginal note for reference 2
- change "42." to "42, 284."
- page 605, new reference
- 19' R. Balasubramanian and K. Soundararajan, “On a conjecture of R. L. Graham,” Acta Arithmetica 75 (1996), 1--38.
- page 607, in reference 51
- change "201" to "309–310"
- page 610, in reference 83
- change '147--223' to '145--223'
- page 611, in reference 98
- change "Basel, 1533" to "Venice, 1482"; also "J. L." to "I. L"
- page 613, in reference 127
- change "J. Fourier" to "Fourier"; also change Sciences par la Société philomathique to Sciences, par la Société philomatique
- page 614, in reference 133
- change 27 to 17
- page 615, in reference 143
- change "123--163" to "123--162"
- page 615, in reference 144
- change "480--490" to "481--490"
- page 617, in reference 174
- change '305.' to '306.' in the margin; also 'G. H. Halphen' to 'Halphen'; also '(1876)' to '(1877)'
- page 621, in reference 235
- change 'della' to 'delle'
- page 628, in reference 330
- change "http://www.research.att.com/~njas/sequences" to "Since 2011, http://oeis.org"
- page 628, append to reference 335
- "Second edition, Cambridge University Press, 1997."
- page 629, in reference 343
- insert a crossreference to page 481 in the margin; and add this: Annotated translation by Ian Tweddle, Springer-Verlag, 2003.
- page 638, Alice entry
- add page 607
- page 638, entry for "answers, notes on"
- move the roman-numeral page "viii" to first position
- page 638, replacement for associative law entry
- associative law, 561
- page 638, new entry
- Balasubramanian, Ramachandran, 525, 605.
- page 639, entries for Boas and Broder
- move the roman-numeral page to first position
- page 639, Borel entry
- put Émile after Justin
- page 639, Branges entry
- change "Branges" to "Branges de Bourcia"
- page 640, Catalan numbers entry
- aadd page 257
- page 641, de Branges entry
- change "Branges" to "Branges de Bourcia"
- page 642, Dieudonné entry
- change "Alexandre" to "Alexandre Eugène"
- page 644, new entry
- Ford, Kevin Barry, 525
- oage 644, Fuss entries
- change "Nicolaĭ" to "Nikolaĭ" and "Fus" to "Fuss"
- page 644, Franel entry
- Franel, Jérôme, 549, 614
- page 645, Ron Graham entry
- add page 605
- page 646, new entry
- Green, Ben Joseph, 525
- page 647, Knopp entry
- change "Konrad" to "Konrad Hermann Theodor"
- page 647. new entry
- Konyagin, Sergei Vladimirovich, 525
- page 647, Lagrange entry
- Lagrange, Joseph Louis (= De la Grange Tournier, Giuseppe Ludovico (= Luigi)), 470, 621, 635
- page 647, Landau entry
- change '622' to '621–622'
- page 648, new entry
- Maynard, James
- page 648, new entry
- McLean, Andrew Stuart, 469
- page 650, Pacioli entry
- Pacioli, Luca Bartolomeo de, 614
- page 650, new entry
- pairing law, 30, 33, 41, 61, 64
- page 652, left column
- regular expressions, 326
- page 653, Schröder entry
- change "Ernst" to "Friedrich Wilhelm Karl Ernst"
- page 653, Schrödinger entry
- change "Erwin" to "Erwin Rudolf Josef Alexander"
- page 653, new entry
- Soundararajan, Kannan, 525, 605.
- page 654, Stirling numbers entry
- change "of the first kind, 259" to "of the first kind (cycle numbers), 259--267
- page 654, Stirling numbers entry
- change "of the second kind, 258" to "of the second kind (set partition numbers), 258--267
- page 655. new entry
- Tao, Terence Chi-Shen, 525
- page 655, new entry
- Tweddle, Ian, 629
- page 656, new entry
- Zudilin, Wadim Valentinovich, 549
Besides those changes, small corrections have been made to “graffiti quotations” on pages 22, 48, 72, 111, 168, 260, 277, 297, 450 in order to make them match the original copy more precisely. Similarly, small corrections have been made to author names and titles in the bibliographic entries for references 44, 50, 64, 76, 77, 85, 99, 107, 135, 158, 192, 195, 199, 210, 223, 229, 232, 236, 240, 274, 284, 285, 292, 296, 297, 304, 309, 318, 321, 336, 343, 347, 357, 359, 361, 370, 371, to make them match the historic record as closely as possible. Slight improvements to spacing and punctuation have also been made silently.
With these corrections, the authors hope that the book is now error-free. But (sigh) it probably isn't. Therefore I 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 1B
Stanford University
Stanford, CA 94305-9015 USA.
In either case please include your postal address, so that I can mail an official certificate of deposit as a token of thanks for any improvements to which you have contributed.
I may not be able to read your message until many months have gone by, because I'm working intensively on The Art of Computer Programming. However, I promise to reply in due time.
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.
Midterm and final exams from the last two times I 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).