View source for Concrete Mathematics

{{Short description|Textbook by Ronald Graham, Donald Knuth, and Oren Patashnik}}
{{Infobox book
| name         = Concrete Mathematics: A Foundation for Computer Science
| title_orig   =
| translator   =
| image        = Concrete Mathematics - Cover.png
| caption      = The cover displays the [[Summation#Capital-sigma notation|mathematical&nbsp;symbol]] for&nbsp;[[summation]],&nbsp;[[Sigma|Σ]], inscribed in&nbsp;[[concrete]].
| author       = [[Ronald Graham]], [[Donald Knuth]], and [[Oren Patashnik]]
| illustrator  =
| cover_artist =
| country      = United States
| language     = English
| series       =
| subject      = [[Mathematics]]<br /> [[Computer science]]
| genre        = 
| publisher    = [[Addison–Wesley]]
| pub_date     = 1994
| media_type   = Print ([[Hardcover]])
| pages        = 657 pp ''(Second Edition)''
| isbn         = 0-201-55802-5
| dewey        = 510 20
| congress     = QA39.2 .G733 1994
| oclc         = 29357079
| preceded_by  =
| followed_by  =
}}

'''''Concrete Mathematics: A Foundation for Computer Science''''', by [[Ronald Graham]], [[Donald Knuth]], and [[Oren Patashnik]], first published in 1989, is a textbook that is widely used in computer-science departments as a substantive but light-hearted treatment of the [[analysis of algorithms]].

== Contents and history ==
The book provides mathematical knowledge and skills for computer science, especially for the [[analysis of algorithms]]. According to the preface, the topics in ''Concrete Mathematics'' are "a blend of CONtinuous and disCRETE mathematics".  [[Calculus]] is frequently used in the explanations and exercises. The term "concrete mathematics" also denotes a complement to "[[abstract mathematics]]".

The book is based on a course begun in 1970 by Knuth at [[Stanford University]]. The book expands on the material (approximately 100 pages)<ref>{{cite web|author=Stenger, Allen|date=18 November 2010|title=Review of ''Concrete Mathematics: A Foundation for Computer Science'', 2nd edition by Ronald L. Graham, Donald E. Knuth, and Oren Patashnik|website=MAA Reviews, Mathematical Association of America|url=https://www.maa.org/press/maa-reviews/concrete-mathematics-a-foundation-for-computer-science}}</ref> in the "Mathematical Preliminaries"<ref>{{cite book|author=Knuth, Donald E.|chapter=Mathematical Preliminaries|title=The Art of Computer Programming, Volume 1. Fundamental Algorithms|edition=3rd|year=1997|isbn=9780321635747|chapter-url=https://books.google.com/books?id=x9AsAwAAQBAJ&q=preliminaries}}</ref> section of Knuth's ''[[The Art of Computer Programming]]''. Consequently, some readers use it as an introduction to that series of books.

''Concrete Mathematics'' has an informal and often humorous style. The authors reject what they see as the dry style of most mathematics textbooks. The margins contain "mathematical [[graffiti]]", comments submitted by the text's first editors: Knuth and Patashnik's students at Stanford.

As with many of Knuth's books, readers are invited to claim a [[Knuth reward check|reward]] for any error found in the book—in this case, whether an error is "technically, historically, typographically, or [[politically incorrect]]".<ref name="GKP"/>

The book popularized some mathematical notation: the [[Iverson bracket]], [[floor and ceiling functions]], and [[Pochhammer symbol#Alternate notations|notation for rising and falling factorials]].

==Typography==
Donald Knuth used the first edition of ''Concrete Mathematics'' as a test case for the [[AMS Euler]] typeface and [[Concrete Roman]] font.<ref name="TUGBoat_1989"/>

==Chapter outline==
{{div col|colwidth=20em}}
# [[Recurrence relation|Recurrent Problems]]
# [[Summation]]
# [[Integer-valued function|Integer Functions]]
# [[Number theory|Number Theory]]
# [[Binomial coefficient|Binomial Coefficients]]
# [[Sequence|Special Numbers]]
# [[Generating function|Generating Functions]]
# [[Discrete probability distribution|Discrete Probability]]
# [[Asymptotic analysis|Asymptotics]]
{{div col end}}

==Editions==
* {{cite book |author-last1=Graham |author-first1=Ronald L. |author-link1=Ronald L. Graham |author-last2=Knuth |author-first2=Donald E. |author-link2=Donald E. Knuth |author-last3=Patashnik |author-first3=Oren |author-link3=Oren Patashnik |title=Concrete Mathematics - A foundation for computer science |edition=1st |series=Advanced Book Program |publisher=[[Addison-Wesley Publishing Company]] |location=Reading, MA, USA |date=1989 |pages=xiv+625 |isbn=0-201-14236-8  |mr=1001562}}
* {{cite book |author-last1=Graham |author-first1=Ronald L. |author-link1=Ronald L. Graham |author-last2=Knuth |author-first2=Donald E. |author-link2=Donald E. Knuth |author-last3=Patashnik |author-first3=Oren |author-link3=Oren Patashnik |title=Concrete Mathematics - A foundation for computer science |edition=2nd |publisher=[[Addison-Wesley Professional]] |location=Reading, MA, USA |date=February 1994 |pages=xiv+657 |isbn=0-201-55802-5 |mr=1397498}} Errata: [http://www-cs-faculty.stanford.edu/~knuth/gkp-err.ps.gz] (1994), [http://www-cs-faculty.stanford.edu/~knuth/gkperr1.html] (January 1998), [http://www-cs-faculty.stanford.edu/~knuth/gkp.html] {{Webarchive|url=https://web.archive.org/web/20201106232418/http://www-cs-faculty.stanford.edu/~knuth/gkp.html |date=2020-11-06 }} (27th [[printing run|printing]], May 2013)

==References==
{{reflist|refs=
<ref name="GKP">[http://www-cs-faculty.stanford.edu/~knuth/gkp.html Graham, Knuth and Patashnik: Concrete Mathematics]</ref>
<ref name="TUGBoat_1989">Donald E. Knuth. ''[http://www.tug.org/TUGboat/Articles/tb10-1/tb23knut.pdf Typesetting Concrete Mathematics]'', TUGboat '''10''' (1989), 31&ndash;36, 342. Reprinted as chapter 18 of the book ''Digital Typography''.</ref>
}}

==External links==
* [https://www.pearson.com/en-us/subject-catalog/p/concrete-mathematics-a-foundation-for-computer-science/P200000000288/9780134389981 ToC and blurb for ''Concrete Mathematics: A Foundation for Computer Science'', 2nd ed.]
* [https://cs.ioc.ee/yik/lib/1/Graham1pre.html Preface for ''Concrete Mathematics: A Foundation for Computer Science'', 2nd ed.]

{{Donald Knuth navbox}}

[[Category:1988 non-fiction books]]
[[Category:Computer science books]]
[[Category:Mathematics textbooks]]
[[Category:Books by Donald Knuth]]
[[Category:Addison-Wesley books]]
[[Category:American non-fiction books]]