Ronald Graham - Concrete Mathematics: A Foundation for Computer Science

ePUB is an open, industry-standard format for eBooks. However, support of ePUB and its many features varies across reading devices and applications. Use your device or app settings to customize the presentation to your liking. Settings that you can customize often include font, font size, single or double column, landscape or portrait mode, and figures that you can click or tap to enlarge. For additional information about the settings and features on your reading device or app, visit the device manufacturers Web site.

Many titles include programming code or configuration examples. To optimize the presentation of these elements, view the eBook in single-column, landscape mode and adjust the font size to the smallest setting. In addition to presenting code and configurations in the reflowable text format, we have included images of the code that mimic the presentation found in the print book; therefore, where the reflowable format may compromise the presentation of the code listing, you will see a Click here to view code image link. Click the link to view the print-fidelity code image. To return to the previous page viewed, click the Back button on your device or app.

Second Edition

A Foundation for Computer Science

Ronald L. Graham

AT&T Bell Laboratories

Donald E. Knuth

Stanford University

Oren Patashnik

Center for Communications Research

Upper Saddle River, NJ Boston Indianapolis San Francisco
New York Toronto Montral London Munich Paris Madrid
Capetown Sydney Tokyo Singapore Mexico City

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 978-0-201-55802-9
1. Mathematics. 2. Computer scienceMathematics. I. Knuth,
Donald Ervin, 1938- . II. Patashnik, Oren, 1954- . III. Title.
QA39.2.G733 1994
510dc20 93-40325
CIP

Internet page http://www-cs-faculty.stanford.edu/~knuth/gkp.html contains current information about this book and related books.

Electronic version by Mathematical Sciences Publishers (MSP), http://msp.org

Copyright 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, mechanical, photocopying, recording, or otherwise, without the prior written permission of the publisher. Printed in the United States of America.

ISBN-13 978-0-201-55802-9
ISBN-10 0-201-55802-5

First digital release, August 2015

Dedicated to Leonhard Euler (17071783)

Audience, level, and treatmenta description of such matters is what prefaces are supposed to be about.

P. R. Halmos []

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 yearjuniors and seniors, but mostly graduate studentsand 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 Hammersley 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 [] 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 hed learned as a mathematics major in college. So he introduced a new course, teaching what he wished somebody had taught him.

People do acquire a little brief authority 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 mathematical problems arising in practice. In short, we look for deeds not words.

J. Hammersley []

The course title Concrete Mathematics was originally intended as an antidote to Abstract Mathematics, since concrete classical results were rapidly 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 theres nothing wrong with it: Its beautiful, general, and useful. But its adherents had become deluded that the rest of mathematics 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 mathematics was becoming inbred and losing touch with reality; mathematical education 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 to teach a math course that was hard instead of soft. He announced that, contrary to the expectations of some of his colleagues, he was not going to teach the Theory of Aggregates, nor Stones Embedding Theorem, nor even the Stoneech compactification. (Several students from the civil engineering department got up and quietly left the room.)

The heart of mathematics consists of concrete examples and concrete problems.

P. R. Halmos []

Although Concrete Mathematics began as a reaction against other trends, the main reasons for its existence were positive instead of negative. And as the course continued its popular place in the curriculum, its subject matter solidified and proved to be valuable in a variety of new applications. Meanwhile, independent confirmation for the appropriateness of the name came from another direction, when Z. A. Melzak published two volumes entitled Companion to Concrete Mathematics [].

It is downright sinful to teach the abstract before the concrete.

Z. A. Melzak []

The material of concrete mathematics may seem at first to be a disparate bag of tricks, but practice makes it into a disciplined set of tools. Indeed, the techniques have an underlying unity and a strong appeal for many people. When another one of the authors (RLG) first taught the course in 1979, the students had such fun that they decided to hold a class reunion a year later.