具体数学第5章二项式系数5.15.3节

第第5章章 二项式系数二项式系数（Binomial Coefficients）E-mail：M.P.：15204679336。书名：具体数学：计算机科学基础（第书名：具体数学：计算机科学基础（第2版）版）原书名：原书名：Concrete Mathematics:A Foundation for Computer Science(2nd Edition)作者：作者：(美美)Ronald L.Graham,Donald E.Knuth,Oren Patashnik译者：张明尧，张凡译者：张明尧，张凡出版社：人民邮电出版社出版社：人民邮电出版社 ISBN：978-7-115-30810-8 第第1章章 递归问题递归问题 第第2章章 和式（选讲）和式（选讲）第第3章章 整值函数整值函数 第第4章章 数论数论 第第5章章 二项式系数二项式系数 第第6章章 特殊的数特殊的数 第第7章章 生成函数（自学）生成函数（自学）第第8章章 离散概率离散概率 第第9章章 渐进式渐进式 It introduces the mathematics that supports the analysis of algorithms,modeling probems in real world.See,Chap.1 Recurrence 递归的计数递归的计数Chap.2 Sum 各种求和，用于算法复杂度计算等各种求和，用于算法复杂度计算等Chap.6 Special Numbers 调和数列及有关求和问题调和数列及有关求和问题 Concrete mathematics is a blending of continuous and discrete mathematics.See,Chap.3 Integer Functions 实数的整数部分运算实数的整数部分运算Chap.9 Asymptotics 离散到连续的渐进离散到连续的渐进 The goal is for the student to have mathematical skills to solve complex problems,and to discover subtle patterns in data.Chap.7 Generating Functions 用于概率计算的母函数用于概率计算的母函数Chap.8 Discrete Probability 离散问题概率离散问题概率(最有趣最有趣)5.1 基本恒等式（基本恒等式（Basic Identities）5.2 基本练习（基本练习（Basic Practice）5.3 处理的技巧（处理的技巧（Tricks of the Trade）85.1 基本恒等式基本恒等式n 组合解释：从组合解释：从n个个不同元素不同元素的集合中选取的集合中选取k个元个元素作为素作为子集（元素无序）子集（元素无序）的方法数。的方法数。9p 10p 根据之前的组合解释，指标仅限于非负整数。但根据之前的组合解释，指标仅限于非负整数。但可打破该限制：可打破该限制：允许上指标取任意实数（甚至复数），允许上指标取任意实数（甚至复数），下指标取任意整数下指标取任意整数。11p 12p 13p 14 帕斯卡三角形帕斯卡三角形n011112121313314146415151010516161520156171721353521718182856705628819193684126 1268436911011045120 210 252 210 1204510115p 16p 17p 18p 19p 20p 21p 22p 23。加法公式的三种截然不同的证明，恰恰说明二项加法公式的三种截然不同的证明，恰恰说明二项式系数有许多有用的性质，其中有一些必定会用来导式系数有许多有用的性质，其中有一些必定会用来导出某个恒等式的证明。出某个恒等式的证明。这是我们需要掌握的工具，或用于证明，或用于这是我们需要掌握的工具，或用于证明，或用于化简，或用于求解复杂的二项式系数的和式。化简，或用于求解复杂的二项式系数的和式。加法公式本质上是关于帕斯卡三角形中的数的递加法公式本质上是关于帕斯卡三角形中的数的递归式，它对使用归纳法证明其他恒等式也很有用。归式，它对使用归纳法证明其他恒等式也很有用。24p 25p 26 27p 28 29对于上述这两个一般的公式，可以利用加法公式，对于上述这两个一般的公式，可以利用加法公式，并通过归纳法进行证明。也可由它们相互给出证明。并通过归纳法进行证明。也可由它们相互给出证明。30p 31p 32p 33p 34p 35p 36p 37p 38p 39p 40p 41p 42p 43犹如二叉树的重要地位，可以基于二项式系数的犹如二叉树的重要地位，可以基于二项式系数的乘积，建立标准技术。乘积，建立标准技术。(5.22)式称为范德蒙德卷积，其它恒等式的基础。式称为范德蒙德卷积，其它恒等式的基础。(5.22)(5.23)(5.24)(5.25)(5.26)44p 45。46上述推导给予的启示：上述推导给予的启示：（1）对所有整数）对所有整数k求和，而不是仅仅在某个范围求和，而不是仅仅在某个范围内求和的巨大便利，可不比过分关注边界条件。内求和的巨大便利，可不比过分关注边界条件。（2）加法公式与数学归纳法能很好地协调。）加法公式与数学归纳法能很好地协调。47p 48p 49最重要的十个二项式系数恒等式。最重要的十个二项式系数恒等式。阶乘展开式阶乘展开式 对称恒等式对称恒等式 吸收吸收/提取恒等式提取恒等式 加法加法/归纳恒等式归纳恒等式 上指标反转上指标反转 三项式版恒等式三项式版恒等式 二项式定理二项式定理 平行求和法平行求和法 上指标求和法上指标求和法 范德蒙德卷积公式范德蒙德卷积公式 5.1 基本恒等式（基本恒等式（Basic Identities）5.2 基本练习（基本练习（Basic Practice）5.3 处理的技巧（处理的技巧（Tricks of the Trade）515.2 基本练习基本练习n 52p 53p 54p 55p n0=1=11=1-1=02=1-3+1=-13=1-7+15-10+1=056p m012345678910110-1-10110-1-157p 58p 59p 60(5.1)P127：阶乘展开式：阶乘展开式(5.4)P129：对称恒等式：对称恒等式(5.5)P129：吸收恒等式：吸收恒等式另有另有(5.6)和和(5.7)(5.8)P130：加法恒等式：加法恒等式(5.9)P132：平行求和法：平行求和法(5.10)P132：上指标求和法：上指标求和法(5.12)P134：二项式定理：二项式定理(5.14)P136：上指标反转法：上指标反转法(5.21)P138：三项式版恒等式：三项式版恒等式表表5-4 最重要的十个二项式系数恒等式最重要的十个二项式系数恒等式61(5.22)式称为范德蒙德卷积，它是其它恒等式的式称为范德蒙德卷积，它是其它恒等式的基础基础(P140)。(5.22)(5.23)(5.24)(5.25)(5.26)62p 63p 64p 65 66p 67p 68p 69p 70p 71p 72p 73p 74p 75p 76p 77p 78p 79p 80p 81p 82p 83p 84p 85p 86p 87最后应用式最后应用式(5.25)，就可得到答案。，就可得到答案。88 5.1 基本恒等式（基本恒等式（Basic Identities）5.2 基本练习（基本练习（Basic Practice）5.3 处理的技巧（处理的技巧（Tricks of the Trade）905.3 处理的技巧处理的技巧n 91p 92。93。94。95。96。97。98。