具体数学-第5章-二项式系数(5.1-5.3节)ppt课件

1、第5章 二项式系数（Binomial Coefficients,鞠成东,E-mail： M. P. 参考教材与书目,参考教材与书目,书名：具体数学：计算机科学基础（第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章 和式（选讲

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 bl

3、ending 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 Disc

4、rete Probability 离散问题概率(最有趣,本章教学内容,5.1 基本恒等式（Basic Identities） 5.2 基本练习（Basic Practice） 5.3 处理的技巧（Tricks of the Trade,8,5.1 基本恒等式,组合解释：从n个不同元素的集合中选取k个元素作为子集（元素无序）的方法数,9,10,根据之前的组合解释，指标仅限于非负整数。但可打破该限制：允许上指标取任意实数（甚至复数），下指标取任意整数,11,12,13,14,帕斯卡三角形,15,16,17,18,19,20,21,22,23,加法公式的三种截然不同的证明，恰恰说明二项式系数有许多有

5、用的性质，其中有一些必定会用来导出某个恒等式的证明。 这是我们需要掌握的工具，或用于证明，或用于化简，或用于求解复杂的二项式系数的和式。 加法公式本质上是关于帕斯卡三角形中的数的递归式，它对使用归纳法证明其他恒等式也很有用,24,25,26,27,28,29,对于上述这两个一般的公式，可以利用加法公式，并通过归纳法进行证明。也可由它们相互给出证明,30,31,32,33,34,35,36,37,38,39,40,41,42,43,犹如二叉树的重要地位，可以基于二项式系数的乘积，建立标准技术。 (5.22)式称为范德蒙德卷积，其它恒等式的基础,44,45,46,上述推导给予的启示： （1）对所有

6、整数k求和，而不是仅仅在某个范围内求和的巨大便利，可不比过分关注边界条件。 （2）加法公式与数学归纳法能很好地协调,47,48,49,最重要的十个二项式系数恒等式。 阶乘展开式 对称恒等式 吸收/提取恒等式 加法/归纳恒等式 上指标反转 三项式版恒等式 二项式定理 平行求和法 上指标求和法 范德蒙德卷积公式,本章教学内容,5.1 基本恒等式（Basic Identities） 5.2 基本练习（Basic Practice） 5.3 处理的技巧（Tricks of the Trade,51,5.2 基本练习,52,53,54,55,56,57,58,59,60,表5-4 最重要的十个二项式系数恒等式,61,5.22)式称为范德蒙德卷积，它是其它恒等式的基础(P140,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,最后应用式(5.25)，就可得到答案,88,本章教学内容,5.1 基本恒等式（Basic