PREFACE ix or chalk.(For example,one of the trademarks of the new design is the symbol for zero,0',which is slightly pointed at the top because a handwritten zero I'm unaccustomed rarely closes together smoothly when the curve returns to its starting point.) to this face. The letters are upright,not italic,so that subscripts,superscripts,and ac- cents are more easily fitted with ordinary symbols.This new type family has been named AMS Euler,after the great Swiss mathematician Leonhard Euler (1707-1783)who discovered so much of mathematics as we know it today. The alphabets include Euler Text(Aa Bb Cc through Xx Yy Zz),Euler Frak- tur (a Bb Cc through 33),and Euler Script Capitals (AB C through X yZ),as well as Euler Greek (Aa BB Ty through XxY Qw)and special symbols such as and We are especially pleased to be able to inaugurate the Euler family of typefaces in this book,because Leonhard Euler's spirit truly lives on every page:Concrete mathematics is Eulerian mathematics. Dear prof:Thanks The authors are extremely grateful to Andrei Broder,Ernst Mayr,An- for (n)the puns, drew Yao,and Frances Yao,who contributed greatly to this book during the (2)the subject matter. years that they taught Concrete Mathematics at Stanford.Furthermore we offer 1024 thanks to the teaching assistants who creatively transcribed what took place in class each year and who helped to design the examination ques- tions;their names are listed in Appendix C.This book,which is essentially a compendium of sixteen years'worth of lecture notes,would have been im- possible without their first-rate work. Many other people have helped to make this book a reality.For example, don't see how we wish to commend the students at Brown,Columbia,CUNY,Princeton, what I've learned Rice,and Stanford who contributed the choice graffiti and helped to debug will ever help me. our first drafts.Our contacts at Addison-Wesley were especially efficient and helpful;in particular,we wish to thank our publisher (Peter Gordon), production supervisor(Bette Aaronson),designer(Roy Brown),and copy ed- itor (Lyn Dupre).The National Science Foundation and the Office of Naval Research have given invaluable support.Cheryl Graham was tremendously helpful as we prepared the index.And above all,we wish to thank our wives I bad a lot of trou- (Fan,Jill,and Amy)for their patience,support,encouragement,and ideas. ble in this class,but We have tried to produce a perfect book,but we are imperfect authors. I know it sharpened my math skills and Therefore we solicit help in correcting any mistakes that we've made.A re- my thinking skills. ward of $2.56 will gratefully be paid to the first finder of any error,whether it is mathematical,historical,or typographical. Murray Hill,New Jersey -RLG and Stanford,California DEK I would advise the May 1988 OP casual student to stay away from this course.I’m unaccustomed to this face. Dear prof: Thanks for (1) the puns, (2) the subject matter. 1 don’t see how what I’ve learned will ever help me. I bad a lot of trou￾ble in this class, but I know it sharpened my math skills and my thinking skills. 1 would advise the casual student to stay away from this course. PREFACE ix or chalk. (For example, one of the trademarks of the new design is the symbol for zero, ‘0’, which is slightly pointed at the top because a handwritten zero rarely closes together smoothly when the curve returns to its starting point.) The letters are upright, not italic, so that subscripts, superscripts, and ac￾cents are more easily fitted with ordinary symbols. This new type family has been named AM.9 Euler, after the great Swiss mathematician Leonhard Euler (1707-1783) who discovered so much of mathematics as we know it today. The alphabets include Euler Text (Aa Bb Cc through Xx Yy Zz), Euler Frak￾tur (%a23236 cc through Q’$lu 3,3), and Euler Script Capitals (A’B e through X y Z), as well as Euler Greek (AOL B fi ry through XXY’J, nw) and special symbols such as p and K. We are especially pleased to be able to inaugurate the Euler family of typefaces in this book, because Leonhard Euler’s spirit truly lives on every page: Concrete mathematics is Eulerian mathematics. The authors are extremely grateful to Andrei Broder, Ernst Mayr, An￾drew Yao, and Frances Yao, who contributed greatly to this book during the years that they taught Concrete Mathematics at Stanford. Furthermore we offer 1024 thanks to the teaching assistants who creatively transcribed what took place in class each year and who helped to design the examination ques￾tions; their names are listed in Appendix C. This book, which is essentially a compendium of sixteen years’ worth of lecture notes, would have been im￾possible without their first-rate work. Many other people have helped to make this book a reality. For example, we wish to commend the students at Brown, Columbia, CUNY, Princeton, Rice, and Stanford who contributed the choice graffiti and helped to debug our first drafts. Our contacts at Addison-Wesley were especially efficient and helpful; in particular, we wish to thank our publisher (Peter Gordon), production supervisor (Bette Aaronson), designer (Roy Brown), and copy ed￾itor (Lyn Dupre). The National Science Foundation and the Office of Naval Research have given invaluable support. Cheryl Graham was tremendously helpful as we prepared the index. And above all, we wish to thank our wives (Fan, Jill, and Amy) for their patience, support, encouragement, and ideas. We have tried to produce a perfect book, but we are imperfect authors. Therefore we solicit help in correcting any mistakes that we’ve made. A re￾ward of $2.56 will gratefully be paid to the first finder of any error, whether it is mathematical, historical, or typographical. Murray Hill, New Jersey -RLG and Stanford, California DEK May 1988 OP