具体数学 第5章 二项式系数(5.4-5.8节)

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-11

2、5-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 Su

3、m 各种求和，用于算法复杂度计算等各种求和，用于算法复杂度计算等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 so

4、lve complex problems, and to discover subtle patterns in data. Chap. 7 Generating Functions 用于概率计算的母函数用于概率计算的母函数Chap. 8 Discrete Probability 离散问题概率离散问题概率(最有趣最有趣) 5.4 生成函数（生成函数（Generating Functions） 5.5 *超几何函数（超几何函数（Hypergeometric Functions） 5.6 *超几何变换（超几何变换（Hypergeometric Transformations） 5.7 *部分超几何

5、和式（部分超几何和式（Partial Hypergeometric Sums） 5.8 *机械求和法（机械求和法（Mechanical Summation）85.4 生成函数生成函数生成函数生成函数方法是离散数学的重要方法，是连方法是离散数学的重要方法，是连接离散数学与连续数学的桥梁接离散数学与连续数学的桥梁。可以说，是离散。可以说，是离散数学数学中最中最令人惊讶的、有益的、巧妙的令人惊讶的、有益的、巧妙的发明。发明。法国法国数学家数学家Laplace 于于1812年出版的年出版的概率概率分析理论分析理论最早提出。最早提出。作用作用：广泛应用于：广泛应用于组合计数组合计数、概率论概率论、证明证

6、明恒等式恒等式、求解递推求解递推关系关系、求求递归数列的通项递归数列的通项公式公式（如：经典的（如：经典的Fibonacci数、数、Catalan数数等）等）以及以及编程与算法设计和编程与算法设计和分析分析（往往对程序效率与速度（往往对程序效率与速度有很大改进有很大改进）等方面。）等方面。91011121314更多应用：更多应用： 利用生成函数利用生成函数证明组合证明组合恒等式恒等式 利用生成函数利用生成函数求解递求解递推推关系关系 常系数线性常系数线性齐次齐次递推关系递推关系 常系数线性常系数线性非齐次非齐次递推关系递推关系 利用生成函数利用生成函数进行组合计数进行组合计数 组合数的生成函数

7、问题组合数的生成函数问题 排列数的指数型生成函数问题排列数的指数型生成函数问题 整数拆分问题整数拆分问题 组合型分配问题组合型分配问题 排列型分配问题排列型分配问题 有限制位置的排列和棋盘多项式问题有限制位置的排列和棋盘多项式问题 利用生成函数利用生成函数解决概率统计问题解决概率统计问题 151617【示例示例2】：求：求n位十进制数中出现偶数个位十进制数中出现偶数个5的数的数的个数。的个数。18192021【练习题练习题】：类似的例子还有许多，例如：著名：类似的例子还有许多，例如：著名的的Hanoi塔问题、塔问题、Fibonacci数列等都是典型的利用生数列等都是典型的利用生成函数求解递推关

8、系的例子。成函数求解递推关系的例子。2223【示例示例4】：若有：若有1克、克、2克、克、3克、克、4克的砝码各克的砝码各一枚，问：能称出哪几种重量？有几种可能方案？一枚，问：能称出哪几种重量？有几种可能方案？24【示例示例4】：若有：若有1克、克、2克、克、3克、克、4克的砝码各克的砝码各一枚，问：能称出哪几种重量？有几种可能方案？一枚，问：能称出哪几种重量？有几种可能方案？【练习题练习题】：若有：若有1克、克、2克的砝码各克的砝码各两两枚，枚，3克、克、4克的砝码各克的砝码各一一枚，问：能称出哪几种重量？有几种枚，问：能称出哪几种重量？有几种可能方案？可能方案？2526【示例示例6】：有红

9、球两只，白球和黄球各一只，：有红球两只，白球和黄球各一只，求有多少种不同的组合方案（颜色和球数不同）。求有多少种不同的组合方案（颜色和球数不同）。27【示例示例6】：有红球两只，白球和黄球各一只，：有红球两只，白球和黄球各一只，求有多少种不同求有多少种不同的组合方案的组合方案（颜色和球数不同）（颜色和球数不同） 。28【示例示例6】：有红球两只，白球和黄球各一只，：有红球两只，白球和黄球各一只，求有多少种不同的组合求有多少种不同的组合方案方案（颜色和球数不同）（颜色和球数不同） 。29【示例示例6】：在做抽样调查时，采访的男士有教：在做抽样调查时，采访的男士有教师、医生、律师等不同的师、医生、

10、律师等不同的q个行业，女士也有不同的个行业，女士也有不同的p个行业，假设我们在每一行业中至多选取个行业，假设我们在每一行业中至多选取2位男士和位男士和至多选取至多选取1位女士，问有多少种不同的方法取位女士，问有多少种不同的方法取k个人的个人的样本？样本？30【示例示例7】：在做抽样调查时，采访的：在做抽样调查时，采访的男士男士来自来自q个不同的行业个不同的行业，女士有女士有p个不同的行业个不同的行业，假设我们在，假设我们在每一行业中至多选取每一行业中至多选取2位男士和至多选取位男士和至多选取1位女士，问位女士，问有多少种不同的方法取有多少种不同的方法取k个人的样本？个人的样本？ (A+B)-(

11、2A+B)x=x.)21)(1()2()()21)(1()1()21(211)(xxxBABAxxxBxAxBxAxH 设设 . 1BA20BA.)12()12()1()221(11211)(22222 xxxxxxxxxH 11)12()(nnnnnnxxhxH, 2 , 1, 12 nhnn).(10655885. 3101536. 31015292. 110718年年 T3839 解解54322235531 )1)(1)(1( ,xxxxxxxxxxG(x)hhnnn 的的生生成成函函数数为为组组合合数数为为设设S 的的1组合数组合数=3：a, b, cS 的的2组合数组合数=5：2a,

12、 2c, ab, ac, bcS 的的3组合数组合数=5：2ab, 2ac, b2c, a2c, abcS 的的4组合数组合数=3：2a2c, 2abc, ab2cS 的的5组合数组合数=1：2ab2c【示例示例9】：S =2a, b,2c , 求求S 的所有的所有n 组合数。组合数。 解解)1)(.(1.)1.)(1()(452xxxxxxg 其其生生成成函函数数为为的的非非负负整整数数解解的的个个数数。是是方方程程种种装装法法。设设共共有有nrrrrhhnn 4321 )1(111111552xxxxx 【示例示例1010】用用n n个水果组成一只个果篮。果个水果组成一只个果篮。果篮中可以

13、装篮中可以装4 4种水果：苹果为偶数，香蕉为种水果：苹果为偶数，香蕉为5 5 的倍数，至多有的倍数，至多有4 4个桔子，至多有一个西个桔子，至多有一个西瓜。可以有多少种装法？瓜。可以有多少种装法？2)1(1x 001)1(nnnnnnxnxC1 nhn所所以以 解解.)(.(1 .).)(1()(24342 xxxxxxxxxg生生成成函函数数为为种种装装法法。设设共共有有nhxxxxxxx 111111522 【示例示例1111】用用n n个水果组成一只个果篮。果个水果组成一只个果篮。果篮中可以装篮中可以装4 4种水果：苹果为偶数，香蕉为种水果：苹果为偶数，香蕉为奇数，至多有奇数，至多有4

14、4个桔子，至少有一个西瓜。个桔子，至少有一个西瓜。可以有多少种装法？可以有多少种装法？22252)1()1()1(xxxx .,8,5,2, 15432 hhhh所所以以.2819148528765432xxxxxxx 解解8642888668448228082870281 )(8xxxxxCxCxCxCCxAan 数数。男男士士中中选选出出偶偶数数的的组组合合表表示示从从设设 【示例示例1212】某某单位有单位有8 8男男5 5女，从中选出一女，从中选出一个小组。要求男士为偶数，女士至少个小组。要求男士为偶数，女士至少2 2人，人，有多少种组合方式？有多少种组合方式？5432551010 5

15、1)1()(25xxxxxxxBbn 人人的的组组合合数数。女女士士中中至至少少选选出出表表示示从从设设 解解 请注意：每个人是有区别的！请注意：每个人是有区别的！1312111098765432538150 350630728840 2812851010 )()()(nxxxxxxxxxxxxxBxAxCcn 组组合合数数。生生成成函函数数为为表表示示满满足足要要求求的的男男女女设设2854222854450825284 CCCCx组组合合数数恰恰为为女女，女女，男男组组合合为为：。的的系系数数人人小小组组的的数数目目为为332815382812851010 为为满满足足要要求求的的所所有有

16、组组合合数数 【示例示例1313】 解解kxxxxg.)()(53 的的生生成成函函数数。数数的的非非负负奇奇数数整整数数解解的的个个求求方方程程nkhnrrr . 21kkkxxxx)1(122 021021rkrrrkrrrrkkxCxCx)(2/ )( ,22/ )(2/ )2(knChknrkrnknknn 得得令令K是偶是偶数，数，N也是也是偶数偶数K是奇是奇数，数，N也是也是奇数奇数【 示例示例1414】 解解.)1(.)1( .)1(.)1()(105428463 xxxxxxxxxg的的生生成成函函数数。求求的的非非负负整整数数解解的的个个数数，是是方方程程nnhnrrrrh

17、432152431,111111115243 xxxxx 解解)1)(1( .)(1.)1.)(1()(50755025105xxxxxxxxg 其其生生成成函函数数为为的的非非负负整整数数解解的的个个数数。是是方方程程种种方方法法。设设共共有有10, 30 5025105 5454321 rrnrrrrrhhnn)1(111111115025100105xxxxxx 【示例示例1616】我们我们有有1 1，5 5，1010，2525，5050等硬等硬币。币。5050分硬币只有分硬币只有1 1个，个，2525分硬币有只有分硬币有只有3 3个，其它硬币有很多。用这些硬币恰好组个，其它硬币有很多。用这些硬币恰好组成成n n分钱，共有多少种方法？分钱，共有多少种方法？ 【示例示例1717】 解解mmmxxxxxxg)1(.)()(32 的