文档详情

第67讲 生成函数(1)

飞***
实名认证
店铺
PPT
526.50KB
约22页
文档ID:3962565
第67讲 生成函数(1)_第1页
1/22

第67讲 生成函数(1),离散数学,8.2 生成函数,第8章 组合计数,第2页,本讲内容,,,第3页,8.2 生成函数,生成函数(generating function)又称为母函数,它是解决满足一定要求的排列组合计数问题的一种重要工具, 也是求解递归关系的一种工具.,第4页,利用生成函数解决计数问题的基本思想就是将要计算的个数ar = f(r) 转化为一个关于x的函数,通过对xr或 的系数的讨论得出结论(r = 0, 1, 2, …).,第5页,8.2.1 组合计数生成函数定义8-1 对于数列a0,a1,…,ar,…,其组合计数生成函数(ordinary generating function)为(形式)幂级数?,第6页,(1) 设n个元素的r-组合个数为ar,r = 0, 1, 2, …. 显然, 有 其组合计数生成函数为,第7页,于是, ar就是其组合计数生成函数 中xr的系数且 实际上, 中第i个(1 + x)可理解为n个元素中的第i个元素,其中的“1”表示在组合中不取第i个元素,“x”表示在组合中选取了第i元素(i = 1, 2, …, n).,第8页,(2) 设n个元素的r-可重组合个数为ar,r = 0, 1, 2, …. 显然, 有特别地a0 = 1. 考虑 其展开式中xr来源于第一个括号(1 + x + x2 + …)中的 , 第二个括号(1 + x + x2 + …)中的 , … , 第n个括号(1 + x + x2 + …)中的 的乘积,即,第9页,这时, 该不定方程的非负整数解的个数为 换句话说,有 因此, 上式右边展开式中xr的系数就是ar.实际上,,第10页,中的第i个(1 + x + x2 + …) 可理解为n个元素中的第i个元素, 其中的“1”表示在组合中不取第i个元素, “x”表示在组合中第i个元素取一次, “x2”表示在组合中第i个元素取了两次, “x3”表示在组合中第i个元素取了三次, …, (i = 1, 2, …, n).,第11页,上述思想还可以推广, 例如在组合计数生成函数中出现乘积项(x2 + x4),则表示对应的元素可取两次或四次.,第12页,(1)(2)(m为实数). (3),第13页,下面通过例子说明如何利用组合计数生成函数解决一般的组合计数问题. 例8-2 口袋中有5个红球, 3个黄球, 绿、白、黑球可任意多提供. 现从中取3个球, 有多少种选取方式?,第14页,Solution 设取r个球的方法有ar种(r = 0, 1, 2, … ), 则组合计数生成函数,第15页,,,第16页,例8-3 现有2n个A, 2n个B, 2n个C, 求从它们中选出3n个字母的方式数.,第17页,Solution 设取r个球的方法有ar种(r = 0, 1, 2, … ), 则组合计数生成函数,第18页,,第19页,,小结与作业,,,第20页,Any Questions,,?,Thank You !,。

下载提示
相似文档
正为您匹配相似的精品文档