CONCRETE
MATHEMATICS
Dedicated to Leonhard Euler (1707-l 783)
CONCRETE
MATHEMATICS
Dedicated to Leonhard Euler (1707-l 783)
CONCRETE
MATHEMATICS
Ronald L. Graham
AT&T Bell Laboratories
Donald E. Knuth
Stanford University
Oren Patashnik
Stanford University
A
ADDISON-WESLEY PUBLISHING COMPANY
Reading, Massachusetts
Menlo Park, California
New York
Don Mills, Ontario
Wokingham, England
Amsterdam
Bonn
Sydney Singapore Tokyo Madrid
San Juan
Library of Congress Cataloging-in-Publication Data
Graham, Ronald Lewis,
1935-
Concrete mathematics
: a foundation for computer science
/
Ron-
ald L. Graham, Donald
E.
Knuth,
Oren
Patashnik.
xiii,625 p.
24 cm.
Bibliography: p. 578
Includes index.
ISBN o-201-14236-8
1.
Mathematics--1961-
2. Electronic data processing--Mathematics.
I. Knuth, Donald Ervin,
1938-
.
II. Patashnik,
Oren,
1954-
.
III. Title.
QA39.2.C733
1988
510--dc19
88-3779
CIP
Sixth printing, with corrections, October 1990
Copyright @ 1989 by Addison-Wesley Publishing Company
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, mechani-
cal,
photocopying, recording, or otherwise, without the prior written permission of
the publisher. Printed in the United States of America. Published simultaneously
in Canada.
FGHIJK-HA-943210
Preface
“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
