线性常系数非齐次递推关系-课件（PPT-精）.pptVIP

§2.8 母函数和递推关系应用举例 例13：设有地址从1到n的单元，用以纪录一组信息。这个信息的每个元素都占用两个单元，而且存放的地址是完全随机的，因而可能出现两个存放信息单元之间留下一个空单元无法存放其他信息，求这n个单元留下空单元的平均数。 设这个平均数为 。 1 2 i+1 i+2 n-1 n 存储单元如上图，设某一信息占用了第i+1，i+2两个单元，把这组单元分割成两个部分，一是从1到i，另一从i+3到n。 * （2-8-13）式是变系数递推关系，可改为 * 由于用相邻两个单元的几率相等， 1 2 i+1 i+2 n-1 n 设 * * §2.10 Stirling数 前面见到的递推关系都是一个参数的。Stirling数导出的递推关系式是两个参数的。 （1）多项式系数 n个有区别的球放到两个有区别的盒子里， 若要求第1个盒子放k个球，第二个盒子放n-k个球 方案数应是 中项 的系数 依据加法法则有 §2.10 Stirling数 可把上面的讨论推广到n个有区别的球放到m个有区别的盒子里，要求m个盒子放的球数分别是 的情况， 其不同方案数用 表示。 从n个有区别的球中取出 个放到第1个盒子里去，其选取方案数为 ； 当第1个盒子的 个球选定后，第2个盒子里的 个球则是从n-n1个中选取的，其方案数应为 ； 第3个盒子的n3个球则是从n-n1-n2中选取，其方案数为 ； §2.10 Stirling数 根据乘法法则有： §2.10 Stirling数 n个有区别的球，放到m个有标志的盒子的问题，也可以考虑把n个有区别的球进行全排列。对于每一个排列依次取n1个放到第1个盒子里，取n2个放到第2个盒子里，…，最后nm个放到第m个盒子里。然而，放到盒子里的球不考虑球的顺序，故得不同的方案数为 称 为多项式系数。 §2.10 Stirling数 多项式 的展开式是由 式右端的n项中，每项各取一个元素相乘而得到的。 表达式 中共有n个因子项，令第i个因子项对应于第i个有标志的球，从第i个因子项中取 对应于把第i个有标志的球放到第i个盒子。 式展开的一般项 表示第一个盒子有 个球，第二个盒子有 个球，等等。因此 式中 项的系数应为 §2.10 Stirling数 定理： 展开式的项数等于C(n+m-1,n) ，而且这些系数之和等于 证明： 展开式中的 项 和从m个 元素 中取n个作允许重复的组合 一一对应。故得 展开式的项数等于C(n+m-1,n), §2.10 Stirling数 从m个中取n个作允许重复的组合的全体，对于每个球都有m个盒子可供选择，根据乘法法则有 §2.10 Stirling数 (2)Stirling数 只准备讨论其中的第二类Stirling数,至 于第一类的Stirling数只准备给出它的定义 和递推关系. 定义: 称 为第一类Stirling数,或用S1表示 显然有 falling factorial 定义: n个有区别的球放到m个相同的盒子中,要求无一空盒,其不同的方案数用 或者 表示,称为第二类Stirling数. 例如红,黄,蓝,白四种颜色的球,放到两个无区别的盒子里,不允许有空盒,其方案有如下七种: 其中r表红球,y表黄球,b表蓝球,w表白球, §2.10 Stirling数 有序拆分的放球模型： n的一个r-分拆相当于把n个无区别的球放到r个有