组合数学第八章.ppt

只准备讨论其中的第二类Stirling数,至于第一类的Stirling数只准备给出它的定义和递推关系. 称 为第一类Stirling数 定义: n个有区别的球放到m个相同的盒子 中,要求无一空盒,其不同的方案数用 表示,称为第二类Stirling数. 例如红,黄,蓝,白四种颜色的球,放到两个无区别的盒子里,不允许有空盒,其方案有如下七种: 其中r表红球,y表黄球,b表蓝球,w表白球, 定理: 第二类Stirling数 有下列性质: (c)设有n个不相同的球 从中取 出球 ,其余的 个球,每个都有与 同盒， 或不与 同盒两种选择. 但必须排除一种情 况,即全体与 同盒,因这时另一盒将是空盒. 故实际上只有 种方案, 即 (d) n个球放到 个盒子里,不允许有一空 盒,故必有一盒有两个球,从n个有区别的球中 取2个共有 种组合方案. 证明: 设有n个有区别的球 从 中取一个球设为 .把n个球放到m个盒子无一 空盒的方案的全体可分为两类。 （a） 独占一盒，其方案数显然为 （b） 不独占一盒，这相当于先将剩下的 个球放到m个盒子，不允许空盒，共 共有 种不同方案，然后将 球放 进其中一盒，从乘法法则得 不独占一盒的 方案数应为 红、黄、蓝、白、绿五个球放到无区别的两 个盒子里。 n个球放到m个盒子里，依球和盒子是否有 区别？是否允许空盒？共有 种状态。 其方案计数分别列于下表。 例: 整数n拆分成1，2，3，…，m的和，并允许重复，求其母函数。如若其中m至少出现一次，其母函数如何？ 若拆分中m至少出现一次，其母函数为： 显然有 一个从上而下的n层格子， 为第 层的格子数，当 ，即上层的格子数不少于下层的格子数时，称之为Ferrers图像，如下图示。 Ferrers图像具有如下性质： 1.每一层至少有一个格子。 2.第一行与第一列互换，第二行于第二列互换，…，即上图绕虚线轴旋转所得的图仍然是Ferrers图像。两个Ferrers图像称为一对共轭的Ferrers图像。 利用Ferrers图像可得关于整数拆分的十分有趣的结果。 (b) 整数n拆分成最多不超过m个数的和的拆分数，和n拆分成最大不超过m的拆分数相等。 拆分成最多不超过m-1个数的和的拆分数的母函数是 所以正好拆分成m个数的和的拆分数的母函数为 (c)整数n拆分成互不相同的若干奇数的和的拆分数,和n拆分成自共轭的Ferrers图像的拆分数相等. 例如 §8.2 Stirling 数 n个球无区别，m个盒子无区别，无空盒时方案计数为 的 项系数。 §8.3 整数拆分 若整数n拆分成1，2，3，…，m的和，并允许重复，其母函数为： §8.3 整数拆分 §8.3 整数拆分 §8.3 整数拆分 上式的组合意义：即整数n拆分成1到m的和的拆分数减去拆分成1到m-1的和的拆分数，即为至少出现一个m的拆分数。 §8.3 整数拆分 §8.3 整数拆分 §8.3 整数拆分 (a) 整数n拆分成k个数的和的拆分数，和数n拆分成最大数为k的若干个数之和的拆分数相等。 因整数n拆分成k个数的和的拆分可用一k行的图像表示。所得的Ferrers图像的共轭图像最上面一行有k个格子。例如： 24=6+6+5+4+3 5个数，最大数为6 24=5+5+5+4+3+2 6个数，最大数为5 §8.3 整数拆分 §8.3 整数拆分 理由和(a)相类似。 因此，拆分成最多不超过m个数的和的拆分数的母函数是 §8.3 整数拆分 所以正好拆分成m个数的和的拆分数的母函数为 §8.3 整数拆分 设 ， 其中 。 构造一个Ferrers图像，其第一行，第一列都是