Preface “A odience,level, THIS BOOK IS BASED on a course of the same name that has been taught and treatment annually at Stanford University since 1970.About fifty students have taken it a description of such matters is each year-juniors and seniors,but mostly graduate students-and alumni what prefaces are of these classes have begun to spawn similar courses elsewhere.Thus the time supposed to be seems ripe to present the material to a wider audience (including sophomores). about.” -P.R.Halmos (142] It was a dark and stormy decade when Concrete Mathematics was born. Long-held values were constantly being questioned during those turbulent years;college campuses were hotbeds of controversy.The college curriculum itself was challenged,and mathematics did not escape scrutiny.John Ham- mersley had just written a thought-provoking article "On the enfeeblement of mathematical skills by 'Modern Mathematics'and by similar soft intellectual trash in schools and universities"[145];other worried mathematicians [272] “People do acquire even asked,"Can mathematics be saved?"One of the present authors had a little brief author- embarked on a series of books called The Art of Computer Programming,and ity by equpping themselves with in writing the first volume he (DEK)had found that there were mathematical jargon:they can tools missing from his repertoire;the mathematics he needed for a thorough, pontificate and aira well-grounded understanding of computer programs was quite different from superficial expertise. But what we should what he'd learned as a mathematics major in college.So he introduced a new ask of educated course,teaching what he wished somebody had taught him. mathematicians is The course title "Concrete Mathematics"was originally intended as an not what they can antidote to "Abstract Mathematics,"since concrete classical results were rap- speecltify about, mor eoen what they idly being swept out of the modern mathematical curriculum by a new wave know about the of abstract ideas popularly called the "New Math!'Abstract mathematics is a existing corpus of mathematical wonderful subject,and there's nothing wrong with it:It's beautiful,general, knowledge.but and useful.But its adherents had become deluded that the rest of mathemat- rather what can ics was inferior and no longer worthy of attention.The goal of generalization they now do with had become so fashionable that a generation of mathematicians had become their leaming and whether they cn unable to relish beauty in the particular,to enjoy the challenge of solving actually solve math- quantitative problems,or to appreciate the value of technique.Abstract math- ematical problems ematics was becoming inbred and losing touch with reality;mathematical ed- arising in practice. ucation needed a concrete counterweight in order to restore a healthy balance In short,we look for deeds not words." When DEK taught Concrete Mathematics at Stanford for the first time, -J.Hammersley (145] he explained the somewhat strange title by saying that it was his attemptPreface “A odience, level, and treatment - a description of such matters is what prefaces are supposed to be about.” - P. R. Halmos 11421 “People do acquire a little brief author￾ity by equipping themselves with jargon: they can pontificate and air a superficial expertise. But what we should ask of educated mathematicians is not what they can speechify about, nor even what they know about the existing corpus of mathematical knowledge, but rather what can they now do with their learning and whether they can actually solve math￾ematical problems arising in practice. In short, we look for deeds not words.” -J. Hammersley [145] THIS BOOK IS BASED on a course of the same name that has been taught annually at Stanford University since 1970. About fifty students have taken it each year-juniors and seniors, but mostly graduate students-and alumni of these classes have begun to spawn similar courses elsewhere. Thus the time seems ripe to present the material to a wider audience (including sophomores). It was a dark and stormy decade when Concrete Mathematics was born. Long-held values were constantly being questioned during those turbulent years; college campuses were hotbeds of controversy. The college curriculum itself was challenged, and mathematics did not escape scrutiny. John Ham￾mersley had just written a thought-provoking article “On the enfeeblement of mathematical skills by ‘Modern Mathematics’ and by similar soft intellectual trash in schools and universities” [145]; other worried mathematicians [272] even asked, “Can mathematics be saved?” One of the present authors had embarked on a series of books called The Art of Computer Programming, and in writing the first volume he (DEK) had found that there were mathematical tools missing from his repertoire; the mathematics he needed for a thorough, well-grounded understanding of computer programs was quite different from what he’d learned as a mathematics major in college. So he introduced a new course, teaching what he wished somebody had taught him. The course title “Concrete Mathematics” was originally intended as an antidote to “Abstract Mathematics,” since concrete classical results were rap￾idly being swept out of the modern mathematical curriculum by a new wave of abstract ideas popularly called the “New Math!’ Abstract mathematics is a wonderful subject, and there’s nothing wrong with it: It’s beautiful, general, and useful. But its adherents had become deluded that the rest of mathemat￾ics was inferior and no longer worthy of attention. The goal of generalization had become so fashionable that a generation of mathematicians had become unable to relish beauty in the particular, to enjoy the challenge of solving quantitative problems, or to appreciate the value of technique. Abstract math￾ematics was becoming inbred and losing touch with reality; mathematical ed￾ucation needed a concrete counterweight in order to restore a healthy balance. When DEK taught Concrete Mathematics at Stanford for the first time, he explained the somewhat strange title by saying that it was his attempt V