《具体数学：计算机科学基础(第 2版)》是一本在大学中广泛使用的经典数学教科书。书中讲解了许多计算机科学中用到的数学知识及技巧，教你如何把一个实际问题一步步演化为数学模型，然后通过计算机解决它，特别着墨于算法分析方面。其主要内容涉及和式、整值函数、数论、二项式系数、特殊的数、生成函数、离散概率、渐近式等，都是编程所必 备的知识。另外，《具体数学：计算机科学基础(第 2版)》包括了六大类500 多道习题，并给出了所有习题的解答，有助读者加深书中内容的理解。 《具体数学：计算机科学基础(第 2版)》面向从事计算机科学、计算数学、计算技术诸方面工作的人员，以及高等院校相关专业的师生

WU

本书源自斯坦福大学每年开设的同名课程，该课程自1970年开设以来，每年有大约50名的选课学生，其中大部分为研究生，还有三、四年级的本科生，这些学生毕业后在其他地方也开设了类似课程﹒因此，是时候将该课程的相关资料呈现给更广泛的读者（包括二年级本科生）了﹒
具体数学诞生之时正是基础理论知识的价值受到质疑的年代，基础理论在大学课程体系中的地位受到了挑战，数学也难逃厄运﹒当时，John Hammersley先生发表了一篇“On the enfeeblement of mathematical skills by‘Modern Mathematics’and by similar soft intellectual trash in schools and universities”（关于高中和大学数学技能被所谓的“现代数学”和类似的软智能垃圾化）的文章[176]，其内容发人深省，还有一些数学家担心[332]：数学还能被保留下来吗？本书的作者之一高德纳（Donald E. Knuth）先生曾以《计算机程序设计艺术》系列书闻名，在写作第1卷时他发现忽略了数学方法，而全面透彻地理解计算机程序设计技巧需要的数学知识完全不同于在大学数学专业所学的数学知识﹒因此，他开设了一门如他所期望的新课程﹒
这门课程取名“具体数学”的初衷是想区别于“抽象数学”，因为在现代数学课程体系中具有抽象概念的“新数学”已经取代了包含具体经典结果的数学﹒抽象数学本身没有任何问题——它完美，通俗，实用，是一门很神奇的学科﹒但是它的崇拜者误导了人们其他数学部分是不值得关注的﹒由于这种概括化思想很盛行，使得一代数学家不能享受数学之美，特别是不能享受解决有挑战性难题的乐趣以及欣赏解题技巧﹒抽象数学曾经历过近亲繁殖阶段，从而使其与现实脱节了，因此，数学教育需要改变以保证其原有的均衡性﹒
当高德纳先生第一次在斯坦福大学教授具体数学（Concrete Mathematics）时，对于有些奇怪的课程名称解释道：想教授一门“硬”数学以代替现在的“软”数学﹒与某些理解相悖（concrete一词在英文中还有另一个意思：混凝土），他声称：不教聚合论，也不讲Stone嵌入定理，更没有Stone-ech紧化﹒（来自土木工程系的学生起身悄悄地离开了教室﹒）
尽管具体数学以逆潮流开始，但是能够存留下来的主要原因是该课程的积极意义﹒作为课程体系中的一门普通课程，它的主要任务是巩固和证明具体数学在各种新的应用中的价值﹒Z. A. Melzak先生出版的两卷本Companion to Concrete Mathematics（与具体数学为伴）[267]，让我们想到了这个名字﹒
具体数学的内容乍看上去好像是放在互不相通袋子里的戏法，但是实际应用使它们有机结合成一套严谨的方法﹒这些技术也确实是和谐统一的，并且具有很强的吸引力﹒作者之一的葛立恒（Ronald L. Graham）先生，1979年首次教授这门课程的时候，学生们兴趣盎然甚至相约一年后的（具体数学）课堂上再相聚﹒
那么，具体数学究竟是什么？是连续数学与离散数学的融合﹒更具体地说，是应用一系列解题方法对数学公式进行可控运算﹒一旦你学过了本书的知识，为了验证看上去令人讨厌的求和，求解复杂的递归关系，以及发现数据中的微妙逻辑关系，你就需要具备冷静的大脑、大量的演算纸，以及相当工整的字迹﹒你的代数学技能必将很熟练，使得你能够很容易地得到精确解而不是仅仅在限定条件下的近似解﹒
本书的主要内容包括求和、递归、初等数论、二项式系数、生成函数、离散概率以及渐近方法﹒此处关注的是这些知识的运算方法而非现有定理或组合推理，其目的是期望每一位读者都能熟悉离散运算（如最大整数函数和有限求和），就像微积分学生熟悉连续运算（如绝对值函数和不定积分）一样﹒
注意，这里的主题列表完全不同于本科生现在所学的“离散数学”课程，因此，课程名称要有所区别，“具体数学”就是再恰当不过的名称了﹒
斯坦福大学具体数学课程的最初教材是《计算机程序设计艺术》中的数学基础部分[207]﹒110页的内容太简略了，这促使另一位本书作者奥伦·帕塔什尼克（Oren Patashnik）先生起草了一份更长一些的补充说明﹒本书现在的版本就是源自这些补充说明，也是对原来“数学基础”内容的扩展及其详细说明﹒一方面，略掉了其中一些更深的知识；另一方面，补充了一些其中没有的内容，使之更加完善了﹒
我们把这些内容都放在本书中的原因是这门学科来源于现实，这本书是原滋原味的呈现﹒而且我们不得不说，以一种我们喜爱的数学方式将这些分布于不同数学分支中不常见的方法放在一起非常合适﹒因此，我们认为，这本书描述的是数学之美和奇妙之处，希望读者能够分享我们写作的喜悦﹒
由于这本书的目的是作为教材，所以尽量采用课堂的教学风格﹒有些人认为数学是严肃的，所以必须是冷冰冰、干巴巴的，而我们则认为数学应该是有趣味的，这也是事实﹒为什么要在工作和趣味之间画一条严格的界限呢？具体数学充满了令人感兴趣的模式，尽管运算是不容易的，但是答案却是神奇而具有魅力的﹒书中鲜明地表现了数学工作的快乐与忧愁——这就是我们的生活﹒
对于课程内容的真实感受，学生远远胜过老师﹒我们将初次学习本教材的学生的感受作为“旁白”放在每一页侧边空白处﹒这些旁白有些是套话，有些很深刻，有些是提醒注意那些含混不清、晦涩难懂的内容，还有些聪明的家伙引用名言名句﹒对于这本书的学习，这些旁白或许有帮助，或许没有帮助，也或许是设置了障碍，但是不管怎么说，它们都是真实情感的表达，有益于内容的消化和理解﹒（采用“旁白”的灵感来源于学生手册Approaching Stanford（走近斯坦福），它同时记录了学校与毕业生双方的观点）﹒例如，学校说：“在这个环境里有些事情不能错过﹒”毕业生说：“环境……什么意思？这里到处都是典型的伪理性主义﹒”学校说：“生活在一起的学生潜力无穷﹒”而毕业生说：“斯坦福的宿舍就像没有管理员的动物园﹒”
旁白也包括史上著名数学家的名言﹒引用最多的有Leibniz、Euler、Gauss以及他们的继承者﹒数学研究不分国界，数学就像由许多金属丝织就的昂贵织物﹒
书中含有500多道练习题，分成6大类：
热身题：首次阅读时应该做的练习﹒
基本题：要亲自动手推导而不是看别人的推导而得到的事实﹒
作业题：更深入地理解相应章节内容的难题﹒
测验题：一道习题涉及两章以上内容，一般来说，用于课下测试（不用于课堂测试是为了不受时间约束）﹒
附加题：超出本书的内容，拓展兴趣﹒
研究题：可做可不做，但值得试一试的难题（没有时间限制）﹒
附录A列出了全部习题答案，并且还包括相关的结果说明（当然，对于研究题的答案是不完全的，即便如此，部分结果和提示对解题也是有帮助的）﹒鼓励读者看答案，特别是热身题的答案，但是希望在认真努力解题之后再看答案﹒
附录C列出的是我们努力找到的习题来源，因为习题设计是一项创造性工作﹒以往数学家使用别人的习题时没有致谢的习惯，国际象棋所采用的方式就是好习惯，如书和杂志引用时一般标明名字、日期、原始棋局的地点﹒然而，对于许多习题我们已经无法找到其原始出处，如果有人知道其出处（这里没有列出来或者列得不准确的），我们非常希望在下一版中更正﹒
本书使用的印刷字体是Hermann Zapf [227]新设计的，得到了美国数学协会的使用许可，并在委员会成员B. Beeton、R. P. Boas、L. K. Durst、D. E. Knuth、P. Murdock、R. S. Palais、P. Renz、E. Swanson、S. B. Whidden以及W. B. Woolf的帮助下发展起来﹒Hermann Zapf的设计理念源于表现数学特色的数学家精美的手写体记法，手写体要比机器风格更贴切，因为人们是用钢笔、铅笔或者粉笔创造数学的（例如：对于符号“0”的新设计打印时稍偏上一点，因为手写体的0在起笔处很少平滑地封闭）﹒字母是垂直不倾斜的，因此上、下标和撇号更容易与普通符号融为一体﹒新字体系列以伟大的瑞士数学家Leonhard Euler（1707—1783）的名字命名，称为“AMS Euler”，Leonhard Euler在数学方面有许多重大发明：字符有Euler Text、Euler Fraktur、Euler Script Capitals、Euler Greek以及特殊符号和等多种字体﹒我们非常高兴能够在本书中开创性地使用Euler系列印刷字体，因为在本书中处处闪烁着Leonhard Euler的思想：具体数学就是Euler的数学﹒
我们非常感谢Andrei Broder、Ernst Mayr、Andrew Yao（姚期智）和Frances Yao（储枫），他们在斯坦福大学教授具体数学的这些年间对这本书做出了巨大的贡献﹒对于助教们每一年创造性的课堂记录以及考试题的设计表示万分感谢，附录C中列出了他们的名字，没有他们的卓越工作，这本书是不可能出版的，因为这本书基本上是16年宝贵教案的集成﹒
还有很多人对本书的出版做出了贡献﹒例如：特别表彰布朗大学、哥伦比亚大学、纽约市立大学（CUNY）、普林斯顿大学、莱斯大学、斯坦福大学的学生们，他们贡献了旁白部分并且对草稿进行了校对﹒与Addison-Wesley的合作效率特别高，特别要感谢出版人Peter Gordon、主管Bette Aaronson、设计师Roy Brown以及编辑Lyn Dupré﹒美国国家科学基金和海军研究院给予了无价的支持﹒Cheryl Graham对于索引给予了极大的帮助﹒感谢我们的妻子们（Fan、Jill和Amy）的耐心、支持、鼓励和建议﹒
第2版最大的变化是新增了5.8节，其中的内容是Doron Zeilberger先生在第1版付印之后不久发现的新的重要思想﹒本书的每一页中都会看到对第1版所做的改进﹒
我们试图创作一部完美的著作，但是我们是不完美的作者，因此，我们期望书中的错误能够得到纠正﹒无论是数学方面的、历史方面的还是印刷方面的，对于每一处错误我们都将奖励第一位发现者2.56美元﹒

计算机科学及应用

本书介绍高级计算机程序设计和算法分析所涉及的数学知识，目的是为解决复杂问题、求解规模庞大的求和问题以及探索数据中的微妙模式提供坚实的数学基础。本书对于每一个涉及数学学科的学生来说都是一本必备的教科书和参考书。
具体数学是连续数学和离散数学的融合。本书讨论的话题是高德纳的经典著作《计算机程序设计艺术》中数学基础部分的扩展，但本书的表达风格更加轻松活泼，对一些主题的讨论更加深入，同时增加了一些新的内容并将重要的思想贯穿全书始末。
书中包含500多道习题，分为6大类。除了研究题外，其余（热身题、基本题、作业题、测验题和附加题）都给出了完整答案，为自学提供了有益的帮助。
本书还在边栏处给出了选修过该课程的学生写的旁白，作者希望在传达数学方法的重要性的同时，增加学生的学习乐趣。

作者简介
葛立恒（Ronald L. Graham） 著名数学家，美国加州大学圣迭戈分校计算机与信息科学专业教席（Jacobs Endowed Chair），AT&T实验室研究中心荣誉首席科学家，美国数学学会前任主席。Graham于1999年成为美国计算机学会会士，2003年获得美国数学学会的斯蒂尔终身成就奖，2012年成为美国数学学会会士。他还曾获得美国数学学会颁发的Lester R. Ford奖和Carl Allendoerfer奖以及其他众多奖项。
高德纳（Donald E. Knuth） 著名计算机科学家，算法与程序设计技术的先驱者、斯坦福大学计算机系荣休教授、计算机排版系统TEX和METAFONT字体系统的发明人，因诸多成就以及大量富于创造力和具有深远影响的著作（19部书，1160篇论文）而誉满全球。Knuth教授获得过许多奖项和荣誉，包括美国计算机学会图灵奖、美国国家科学奖章、美国数学学会的斯蒂尔奖，以及因发明先进技术于1996年荣获的京都奖。1996年，设立了以其名字命名的Donald E. Knuth奖，授予那些为计算机科学基础做出杰出贡献的人。
奥伦·帕塔什尼克（Oren Patashnik） 著名计算机科学家，BibTeX的创始人之一。他在1976年毕业于耶鲁大学，后来在斯坦福大学师从高德纳，1980年就职于贝尔实验室。1985年与Leslie Lamport合作创建了BibTeX（LaTeX的一种工具，用于管理文献、产生文献目录）。

[美]葛立恒（Ronald L. Graham）高德纳（Donald E. Knuth） 奥伦·帕塔什尼克（Oren Patashnik） 著：葛立恒（Ronald L. Graham） 著名数学家，美国加州大学圣迭戈分校计算机与信息科学专业教席（Jacobs Endowed Chair），AT&T实验室研究中心荣誉首席科学家，美国数学学会前任主席。Graham于1999年成为美国计算机学会会士，2003年获得美国数学学会的斯蒂尔终身成就奖，2012年成为美国数学学会会士。他还曾获得美国数学学会颁发的Lester R. Ford奖和Carl Allendoerfer奖以及其他众多奖项。
高德纳（Donald E. Knuth） 著名计算机科学家，算法与程序设计技术的先驱者、斯坦福大学计算机系荣休教授、计算机排版系统TEX和METAFONT字体系统的发明人，因诸多成就以及大量富于创造力和具有深远影响的著作（19部书，1160篇论文）而誉满全球。Knuth教授获得过许多奖项和荣誉，包括美国计算机学会图灵奖、美国国家科学奖章、美国数学学会的斯蒂尔奖，以及因发明先进技术于1996年荣获的京都奖。1996年，设立了以其名字命名的Donald E. Knuth奖，授予那些为计算机科学基础做出杰出贡献的人。
奥伦•帕塔什尼克（Oren Patashnik） 著名计算机科学家，BibTeX的创始人之一。他在1976年毕业于耶鲁大学，后来在斯坦福大学师从高德纳，1980年就职于贝尔实验室。1985年与Leslie Lamport合作创建了BibTeX（LaTeX的一种工具，用于管理文献、产生文献目录）。

1　递归问题 1
1.l　汉诺塔问题 1
1.2　直线划分平面问题 4
1.3　约瑟夫问题 8
习题 17
2　求和 21
2.1　表示法 21
2.2　求和与递归 25
2.3　求和的运算方法 30
2.4　多重求和 34
2.5　求和方法一览 41
2.6　差分与求导 47
2.7　无穷项求和问题 56
习题 62
3　整数函数 67
3.1　向上取整函数和向下取整函数 67
3.2　取整函数的应用 70
3.3　取整函数的递归表示法 78
3.4　mod：二元运算 81
3.5　取整函数的求和 86
习题 95
4　数论 102
4.1　整除性 102
4.2　素数 105
4.3　素数示例 107
4.4　阶乘的因子 111
4.5　互质 115
4.6　mod：同余关系 123
4.7　独立余数 126
4.8　应用 129
4.9　欧拉函数与默比乌斯函数 133
习题 144
5　二项式系数 153
5.1　基本恒等式 153
5.2　基本练习 172
5.3　应用技巧 186
5.4　生成函数 196
5.5　超几何函数 204
5.6　超几何变换 216
5.7　超几何部分求和 223
5.8　算法化求和 229
习题 242
6　特殊数 257
6.1　斯特林数 257
6.2　欧拉数 267
6.3　调和数 272
6.4　调和级数求和 279
6.5　伯努利数 283
6.6　斐波那契数列 290
6.7　连续式 301
习题 309
7　生成函数 320
7.1　多米诺理论与零钱支付方案 320
7.2　基本策略 331
7.3　递归式求解 337
7.4　特殊生成函数 350
7.5　卷积运算 353
7.6　指数型生成函数 364
7.7　狄利克雷生成函数 370
习题 371
8　离散概率 381
8.1　定义 381
8.2　均值与方差 387
8.3　概率生成函数 394
8.4　掷硬币 401
8.5　哈希法 411
习题 427
9　渐近理论 439
9.1　渐近量级 440
9.2　O记法 443
9.3　O运算 450
9.4　两个渐近技巧 463
9.5　欧拉求和公式 469
9.6　结论 476
习题 489
A　习题答案 497
B　参考文献 604
C　习题来源 632

Contents
1 Recurrent Problems 1
1.1 The Tower of Hanoi 1
1.2 Lines in the Plane 4
1.3 The Josephus Problem 8
Exercises 17
2 Sums 21
2.1 Notation 21
2.2 Sums and Recurrences 25
2.3 Manipulation of Sums 30
2.4 Multiple Sums 34
2.5 General Methods 41
2.6 Finite and Infinite Calculus 47
2.7 Infinite Sums 56
Exercises 62
3 Integer Functions 67
3.1 Floors and Ceilings 67
3.2 Floor/Ceiling Applications 70
3.3 Floor/Ceiling Recruuences 78
3.4 'mod': The Binary Operation 81
3.5 Floor/Ceiling Sums 86
Exercises 95
4. Number Theory 102
4.1 Divisibility 102
4.2 Primes 105
4.3 Prime Examples 107
4.4 Factorial Factors 111
4.5 Relative Primality 115
4.6 'mod': The Congruence Relation 123
4.7 Independent Residues 126
4.8 Additional Applications 129
4.9 Phi and Mu 133
Exercises 144
5 Binomaial Coefficients 153
5.1 Basic Indentities 153
5.2 Basic Practice 172
5.3 Tricks of the Trade 186
5.4 Generating Functions 196
5.5 Hypergeometric Functions 204
5.6 Hypergeometric Transformations 216
5.7 Pratial Hypergeometric Sums 223
5.8 Mechanical Summation 229
Exercises 242
6 Special Numbers 257
6.1 Stirling Numbers 257
6.2 Eulerian Numbers 267
6.3 Harmonic Numbers 272
6.4 Harmonic Summation 279
6.5 Bernoulli Numbers 283
6.6 Fibonacci Numbers 290
6.7 Continuants 301
Exercises 309
7 Generating Functions 320
7.1 Domino Theory and Change 320
7.2 Basic Maneuvers 331
7.3 Solving Recurrences 337
7.4 Special Generating Functions 350
7.5 Convolutions 353
7.6 Exponential Generating Functions 364
7.7 Dirichlet Generating Functions 370
Exercises 371
8 Discrete Probability 381
8.1 Definitions 381
8.2 Mean and Variance 387
8.3 Probability Generating Functions 394
8.4 Flipping Coins 401
8.5 Hashing 411
Exercises 427
9 Asymptotics 439
9.1 A Hierarchy 440
9.2 O Notation 443
9.3 O Manipulation 450
9.4 Two Asymptotic Tricks 463
9.5 Euler's Summation Formula 469
9.6 Final Summations 476
Exercises 489
A Answers to Exercises 497
B Bibliography 604
C Credits for Exercises 632