组合数学（张永刚）吉林大学 第五章 生成函数.pptVIP

（2） 根据定理 3.6.3知，将n分拆为k个分部（每一分部的大小不受限制）的分拆数等于将n分拆为最大分部为k（分部个数不限）的分拆数，其分拆数相当于求方程 的整数解的个数，其生成函数为 * 其中展开式中 的系数即为n的最大分项等于k的分拆个数. 其他法易证明： ，因此 若 ，则 ，因此当 ，它们对应的生成函数的系数为零，所以 * 推论 n 的各分部量两两互不相同的分拆数等于 n的各分部量是奇数的分拆数。 证明 n的各分部量两两互不相同的分拆数的生成函数为 而 显然是n的各分部量是奇数的分拆 数数列的生成函数，因此结论成立. * 例 用1角、2角、3角的邮票贴出面值6角，求有多少种不同的方案？ 解 这是可重复的无序分拆，相应的生成函数为 显然所求为 的系数，为7，说明贴出6角面值的方案有7种。具体为： 6= 1 + 1 + 1 + 1，6 = 2 + 2 + 2，6 = 2 + 2 + 1 + 1， 6=2 + 1 + 1 + 1 + 1，6=3 + 3， 6=3 + 2 + 1，6=3 + 1 + 1 + 1. 例5.5.1中，若考虑不同面值贴的顺序，则有多少种方案。 * 6= 1 + 1 + 1 + 1， 6 = 2 + 2 + 2， 6 = 2 + 2 + 1 + 1， 6=2 + 1 + 1 + 1 + 1， 6=3 + 3， 6=3 + 2 + 1， 6=3 + 1 + 1 + 1. 推论5.2.1 设 ，若限定在k-组合中元素 出现的次数集合为 ，则从M的k-组合数 对应序列 的生成函数为 例5.2.1 利用生成函数方法求 的k-组合数。 * 解 设 的k-组合数为 ，则数列{ }的生成函数为： 其中 的系数就是 M 的k-组合数 ， 这个结果显然与第三章中定理3.3.3是一致的。 * 在普通集合 的k -组合中， 或出现或不出现，故其k -组合数数列{ }的生成函数为 从而 例5.2.3 求 的每个元素至少取一次的k-组合数。 * 解 设 的每个元素至少取一次的k-组合数 对应数列 的生成函数为 为 的系数 。 * （变量替换：n+k=m） 例5.2.4 求方程 　　 的整数解的个数。 解：设方程的 整数解数为 ，数列 对应的生成函数为 我们所求的是 为 展开式中 的系数 * 例5.2.5 求方程 x1+2x2=15 的非负整数解的个数。 解 设方程 x1+2x2=k 的非负整数解的个数为 ak , {ak}的生成函数为 因此， a15=8. * 其中，有理分式中P(x)的次数小于Q (x)的次数。 例5.2.6 假定有足够多的苹果、香蕉、橘子和梨，用这4种水果装