C O N C R E T E
M AT H E M AT I C S
Second Edition
Dedicated to Leonhard Euler (1707{1783)
A Foundation for Computer Science
C O N C R E T E
M AT H E M AT I C S
Second Edition
Ronald L. Graham
AT&T Bell Laboratories
Donald E. Knuth
Stanford University
Oren Patashnik
Center for Communications Research
6
77
ADDISON-WESLEY PUBLISHING COMPANY
Reading, Massachusetts Menlo Park, California New York
Don Mills, Ontario Wokingham, England Amsterdam Bonn
Sydney Singapore Tokyo Madrid San Juan Milan Paris
Library of Congress Cataloging-in-Publication Data
Graham, Ronald Lewis, 1935-
Concrete mathematics : a foundation for computer science / Ronald
L. Graham, Donald E. Knuth, Oren Patashnik. -- 2nd ed.
xiii,657 p. 24 cm.
Bibliography: p. 604
Includes index.
ISBN 0-201-55802-5
1. Mathematics. 2. Computer science--Mathematics. I. Knuth,
Donald Ervin, 1938- . II. Patashnik, Oren, 1954- . III. Title.
QA39.2.G733 1994
510--dc20 93-40325
CIP
Reproduced by Addison-Wesley from camera-ready copy supplied by the authors.
Copyright
c
°
1994, 1989 by Addison-Wesley Publishing Company, Inc.
All rights reserved. No part of this publication may be reproduced, stored in a
retrieval system, or transmitted, in any form or by any means, electronic, mechan-
ical, photocopying, recording, or otherwise, without the prior written permission
of the publisher. Printed in the United States of America.
1 2 3 4 5 6 7 8 9 10{MA{9897969594
Preface
THIS BOOK IS BASED on a course of the same name that has been taught
\Audience, level,
and treatment|
a description of
such matters is
what prefaces are
supposed to be
about."
|P.R.Halmos [173]
annually at Stanford University since 1970. About fty 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" [176]; other worried mathematicians [332]
even asked, \Can mathematics be saved?" One of the present authors had
\People do acquire a
little brief author-
ity by equipping
themselves with
jargon: they can
ponticate and air a
supercial 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 [176]
embarked on a series of books called
The Art of Computer Programming
, and
in writing the rst 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 dierent 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 rst time,
he explained the somewhat strange title by saying that it was his attempt
v
