''Concrete Mathematics: A Foundation for Computer Science'', by

Ronald Graham Ronald Lewis Graham (October 31, 1935July 6, 2020) was an American mathematician credited by the American Mathematical Society as "one of the principal architects of the rapid development worldwide of discrete mathematics in recent years". He ...

Donald Knuth Donald Ervin Knuth ( ; born January 10, 1938) is an American computer scientist and mathematician. He is a professor emeritus at Stanford University. He is the 1974 recipient of the ACM Turing Award, informally considered the Nobel Prize of comp ...

, 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 In computer science, the analysis of algorithms is the process of finding the computational complexity of algorithms—the amount of time, storage, or other resources needed to execute them. Usually, this involves determining a function that r ...

Contents and history

The book provides mathematical knowledge and skills for computer science, especially for the

. According to the preface, the topics in ''Concrete Mathematics'' are "a blend of CONtinuous and disCRETE mathematics".

Calculus Calculus is the mathematics, mathematical study of continuous change, in the same way that geometry is the study of shape, and algebra is the study of generalizations of arithmetic operations. Originally called infinitesimal calculus or "the ...

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 Leland Stanford Junior University, commonly referred to as Stanford University, is a Private university, private research university in Stanford, California, United States. It was founded in 1885 by railroad magnate Leland Stanford (the eighth ...

. The book expands on the material (approximately 100 pages) in the "Mathematical Preliminaries" section of Knuth's ''

The Art of Computer Programming ''The Art of Computer Programming'' (''TAOCP'') is a comprehensive multi-volume monograph written by the computer scientist Donald Knuth presenting programming algorithms and their analysis. it consists of published volumes 1, 2, 3, 4A, and 4 ...

''. 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 Graffiti (singular ''graffiti'', or ''graffito'' only in graffiti archeology) is writing or drawings made on a wall or other surface, usually without permission and within public view. Graffiti ranges from simple written "monikers" to elabor ...

", 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 reward for any error found in the book—in this case, whether an error is "technically, historically, typographically, or

politically incorrect "Political correctness" (adjectivally "politically correct"; commonly abbreviated to P.C.) is a term used to describe language, policies, or measures that are intended to avoid offense or disadvantage to members of particular groups in society. ...

". The book popularized some mathematical notation: the

Iverson bracket In mathematics, the Iverson bracket, named after Kenneth E. Iverson, is a notation that generalises the Kronecker delta, which is the Iverson bracket of the statement . It maps any statement to a function of the free variables in that statement. ...

floor and ceiling functions In mathematics, the floor function is the function that takes as input a real number , and gives as output the greatest integer less than or equal to , denoted or . Similarly, the ceiling function maps to the least integer greater than or eq ...

, and 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.

Chapter outline

# Recurrent Problems #

Summation In mathematics, summation is the addition of a sequence of numbers, called ''addends'' or ''summands''; the result is their ''sum'' or ''total''. Beside numbers, other types of values can be summed as well: functions, vectors, matrices, pol ...

# Integer Functions #

Number Theory Number theory is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic functions. Number theorists study prime numbers as well as the properties of mathematical objects constructed from integers (for example ...

Binomial Coefficients In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers and is written \tbinom. It is the coefficient of the te ...

# Special Numbers #

Generating Functions In mathematics, a generating function is a representation of an infinite sequence of numbers as the coefficients of a formal power series. Generating functions are often expressed in closed form (rather than as a series), by some expression invo ...

# Discrete Probability #

Asymptotics In mathematical analysis, asymptotic analysis, also known as asymptotics, is a method of describing limiting behavior. As an illustration, suppose that we are interested in the properties of a function as becomes very large. If , then as bec ...

Editions

* * Errata

(1994)

(January 1998)

(27th printing run, printing, May 2013)

References

External links

ToC and blurb for ''Concrete Mathematics: A Foundation for Computer Science'', 2nd ed.

{{Donald Knuth navbox 1988 non-fiction books Computer science books Mathematics textbooks Books by Donald Knuth Addison-Wesley books American non-fiction books