组合数学讲义及答案 2章 母函数.pdf

组合数学 第二章 母函数 1/49 第 二 章第 二 章 母 函 数 及 其 应 用母 函 数 及 其 应 用 问题问题：对于不尽相异元素的部分排列和组合，用第一章的方对于不尽相异元素的部分排列和组合，用第一章的方 法是比较麻烦的（参见表法是比较麻烦的（参见表 2.0.1） 。） 。 新方法新方法：母函数方法。母函数方法。 表表 2.0.1 条件条件 组合方案数组合方案数 排列方案数排列方案数 对应的集合对应的集合 相异元素，不重复相异元素，不重复 ! ! rnr n C r n ! ! rn n P r n n eeeS, 21 相异元素，可重复相异元素，可重复 r rn C 1 r n S, 21 ee n e , 不尽不尽 相异相异 元素元素 （有（有 限重限重 复）复） 特例特例 rn 1 ! ! 21m nnn n S 11 en ， 22 en ， mm en , n1n2nm n，nk1, (k1,2, m) r1 m m 所有所有 k nr r rm C 1 r m 至少有一个至少有一个 k n 满足满足 1 k n 2 n k n 构造一个构造一个 Ferrers 图，其第一行、第一列都是图，其第一行、第一列都是 1 n1，对应于，对应于 2 2 n 1，第二行、第二列都是，第二行、第二列都是 2 n1，对应于，对应于 2 2 n1，依此类推。由此，依此类推。由此 所得的所得的 Ferrers 图是自共轭的。反过来也一样。例如图是自共轭的。反过来也一样。例如 17953 对应的对应的 Ferrers 图如图图如图 2.4.2 所示。所示。 图图 2.4.2 n 分拆为不同的奇数及其对应的自共轭的分拆为不同的奇数及其对应的自共轭的 Ferrers 图图 2.4.4 分拆数的估计分拆数的估计 对于对于 n 的的 k 无序分拆，当无序分拆，当 k 任意时（任意时（k1,2,n） ，） ，n 的所有分的所有分 拆的个数称作拆的个数称作 n 的分拆数，记作的分拆数，记作 p(n)，即，即 n k k npnp 1 定理定理2.4.32.4.3 正整数正整数 n 的全部分拆总数数列的全部分拆总数数列 np的母函数是的母函数是 0n n xnpxP k xxx 111 1 2 （2.4.8） 当当 n 较大时，计算较大时，计算 p(n)是非常困难的，例如是非常困难的，例如 p(1)1， p(5)7， p(10)42， p(15)176，p(20)627， p(25)1958， p(200)39729990293884 万亿万亿 下面给出下面给出 p(n)的渐进公式和估值不等式。的渐进公式和估值不等式。 定理定理2.4.42.4.4 关于关于 np的计算，有的计算，有 （1） n np 3 20 e 组合数学 第二章 母函数 30/49 （2） n n np n , 3 2 34 1 e （3） nn nnp 3 2 ， n2 . 还有一种利用二元递归函数来计算还有一种利用二元递归函数来计算 p(n)的算法，描的算法，描 述如下。述如下。 定理定理2.4.52.4.5 设函数设函数mnQ,表示正整数表示正整数 n 的最大分项的最大分项 n1m 的所的所 有分拆数，则有有分拆数，则有 nmmmnQmnQ nmnnQ nmnnQ nm mnQ 11 11 111 , , , , , 或或 （2.4.9） 定理定理 2.4.5 实质上是函数实质上是函数 Q(n,m)的递归定义， 其原因的递归定义， 其原因 如下：如下： (1) 显然有显然有 Q(1,n) Q(m,1)1； (2) 因为最大分量因为最大分量 n1实际上不能大于实际上不能大于 n，故，故 m n 时，时，Q(n,m) Q(n,n)； (3) 由于在由于在 n 的所有分拆中，其的所有分拆中，其 1 分拆只有一个，即分拆只有一个，即 n n1， 而其它的分拆都是而其它的分拆都是 n1n-1； (4) 因为对于正整数因为对于正整数 n，最大分项为，最大分项为 m 的分拆数由以下两部分的分拆数由以下两部分 组成：一个是以组成：一个是以 m 作为第一分项，其余分项之和等于作为第一分项，其余分项之和等于 nm，且，且 最大分项最大分项 n2不超过不超过 m 的分拆数的分拆数 Q(n-m,m)；另一个是最大分项；另一个是最大分项 n1 m-1 的分拆数的分拆数(n，m-1)。 根据以上定义，可看出根据以上定义，可看出 np nnQ,。因此计算。因此计算 np的问题便的问题便 归结为计算递归函数归结为计算递归函数 mnQ,。 组合数学 第二章 母函数 31/49 2.4.5 应用应用 例例2.4.12.4.1 （各分项不同，即不各分项不同，即不重复重复）设有）设有 1 克、克、2 克、克、3 克、克、4 克的砝码各一枚，若要求各砝码只能放在天平的一边。问能称出克的砝码各一枚，若要求各砝码只能放在天平的一边。问能称出 那几种重量？有哪几种可能方案？那几种重量？有哪几种可能方案？ （解解）这是典型的正整数分拆问题。比如说可以称）这是典型的正整数分拆问题。比如说可以称 6 克重的克重的 物品，使用的砝码可以是物品，使用的砝码可以是 1 克、克、2 克、克、3 克的三个砝码放在一起，克的三个砝码放在一起， 也可以是也可以是 2 克和克和 4 克的两个砝码放在一起来称。即当最大分项不克的两个砝码放在一起来称。即当最大分项不 超过超过 4 时，时，6 的无序不重复分拆只有两种的无序不重复分拆只有两种 632142 首先， 将整数首先， 将整数 n 分拆为最大分项不超过分拆为最大分项不超过 4， 且各分项最多只能， 且各分项最多只能 出现一次的分拆数数列的母函数为（即在式（出现一次的分拆数数列的母函数为（即在式（2.4.6）中令）中令 0 i x 1 而得而得到的式（到的式（2.4.7）的特殊情形）的特殊情形） 432 1111xxxx 1098765432 222221xxxxxxxxxx 从右端的母函数知可称出从从右端的母函数知可称出从 1克到克到 10克共克共10种重量， 幂种重量， 幂 n x的的 系数即为称出系数即为称出 n 克重量的方案数。克重量的方案数。 若要枚举出具体的称重方案，则分拆数的母函数应为若要枚举出具体的称重方案，则分拆数的母函数应为 432 1111wzyx （2.4.10） 1xy2(xy2z3)(xz3w4) 4232 wyzxy 324 zyxw 4342 wzwxy 43w xzy2z3w4 xy2z3w4 从式中可以看出，从式中可以看出， 若若 4321 nnnn wzyx（ i n0 或或i）中各因子）中各因子 的指数之和为的指数之和为 n，则该单项式，则该单项式 4321 nnnn wzyx就对应一种称就对应一种称 n 克重克重 量的方案。如量的方案。如 z3w4就是称就是称 7 克重量的方案之一，而且用的是克重量的方案之一，而且用的是 3 克克 和和 4 克的砝码。称克的砝码。称 7 克重量的另一方案则是克重量的另一方案则是 xy2w4对应的用对应的用 1 克、克、 2 克和克和 4 克的砝码。克的砝码。 说明说明： 组合数学 第二章 母函数 32/49 （1） 取取 12324，重量相同，元素个数不同，重量相同，元素个数不同，对应所取对应所取 元素个数元素个数不同的组合方案。不同的组合方案。 （2） 若取两个元素，如若取两个元素，如 235，347，元素个数相同，元素个数相同， 但重量不同，是不同的整数的分拆方案。但重量不同，是不同的整数的分拆方案。 （3） 组合关心的是元素的个数，本题关心的是元素的加权和组合关心的是元素的个数，本题关心的是元素的加权和 （每个元素赋予一定的权值） 。（每个元素赋予一定的权值） 。对于组合而言，其母函数对于组合而言，其母函数 应为应为 wzyx 1111 1（xyzw）（xyxzxwyzywzw） （xyzxywxzwyzw）xyzw 例例2.4.22.4.2 （各分项无限重复各分项无限重复）求用）求用 1 分、分、2 分、分、3 分的邮票贴出分的邮票贴出 不同面值的方案数。不同面值的方案数。 解解 这是可重复的无序分拆，相应的母函数为这是可重复的无序分拆，相应的母函数为 G(x)(1xx2)(1x2x4)(1x3x6 ) 32 1 1 1 1 1 1 xxx 6543 1 1 xxxxx 65432 754321xxxxxx 以以 4 x为例，其系数等于为例，其系数等于 4，说明贴出，说明贴出 4 分面值的方案有分面值的方案有 4 种，种， 即即 41111， 4211， 422， 431 这里是按照邮票总面值的不同来区别并统计方案数的。若将这里是按照邮票总面值的不同来区别并统计方案数的。若将 邮票贴成一行，不同面值的邮票互换位置后算作另一种方案，则邮票贴成一行，不同面值的邮票互换位置后算作另一种方案，则 问题将成为有序分拆。问题将成为有序分拆。 例例2.4.32.4.3 （有序分拆有序分拆）在例）在例 2.4.2 中，按照有序分拆，贴成总面中，按照有序分拆，贴成总面 值等于值等于 4 分的方案数是多少？分的方案数是多少？ 组合数学 第二章 母函数 33/49 解解 这时，在无序分拆中的分拆方案这时，在无序分拆中的分拆方案 4211、431 将分别对应将分别对应 3 个和个和 2 个有序分拆方案个有序分拆方案 4211121112， 43113 所以，总的方案数应为所以，总的方案数应为 7。 这里也可以利用定理这里也可以利用定理 2.4.1 的推论来计算方案数：的推论来计算方案数： 4 的的 1 有序分拆数为有序分拆数为 4 1 qC(4-1，1-1)1，即，即 44 分拆为分拆为 自身；自身； 4 的的 2 有序分拆数为有序分拆数为 4 2 qC(4-1，2-1)3，即，即 4311 322； 4 的的 3 有序分拆数为有序分拆数为 4 3 qC(4-1，3-1)3，即，即 4211 121112； 4 的的 4 有序分拆数为有序分拆数为 4 4 qC(4-1，4-1)1，即，即 4111 1。 各项各项 4 i q求和，即得求和，即得 4 的全部有序分拆数为的全部有序分拆数为 8，但本题中无，但本题中无 4 分面值的邮票，故不算分面值的邮票，故不算 4 1 q，恰为，恰为 7 种方案。种方案。 例例2.4.42.4.4 （各分项有限不重复各分项有限不重复）若有）若有 1 克的砝码克的砝码 3 枚，枚，2 克的克的 4 枚，枚，4 克的克的 2 枚，问能称出多少种重量？各有几种方案？枚，问能称出多少种重量？各有几种方案？ 解解 这是无序分拆中处于不重复分拆（见例这是无序分拆中处于不重复分拆（见例 2.4.1）和无限重）和无限重 复分拆（见例复分拆（见例 2.4.2）之间的有限重复分拆问题，作为式（）之间的有限重复分拆问题，作为式（2.4.7） 的特例，其母函数为的特例，其母函数为 G(x) 84864232 111xxxxxxxxx 1x2x22x33 x43x54x64x75x85x95x10 5 x114 x124 x133 x143 x152 x162 x17x18 x19 组合数学 第二章 母函数 34/49 共能称出共能称出 19 种重量，各种重量的方案数即为各种重量，各种重量的方案数即为各 n x的的系数。的的系数。 例如，称例如，称 8 克重量，即克重量，即 8 的分项为的分项为 1、2、4 的无序分拆有的无序分拆有 8 444224211222222211 若将若将 1 克的砝码改为克的砝码改为 4 枚，显然，称枚，显然，称 8 克重量的方案还有克重量的方案还有 8 41111221111 相应的母函数以及称其它重量的方案情况。相应的母函数以及称其它重量的方案情况。 例例2.4.52.4.5 (扩展扩展)： 在例在例 2.4.4 中， 若砝码可以放在天平的两边，中， 若砝码可以放在天平的两边， 但两边不但两边不能同时有同样重量的砝码，请给出问题的母函数。问要能同时有同样重量的砝码，请给出问题的母函数。问要 秤出秤出 2 克重的物体，有多少种不同的秤法？并给出每一种秤法。克重的物体，有多少种不同的秤法？并给出每一种秤法。 解解 此时，物体一边的砝码实际起了抵消天平另一边砝码重量此时，物体一边的砝码实际起了抵消天平另一边砝码重量 的作用。故称重量问题的母函数为的作用。故称重量问题的母函数为 G(x) 32 23 1 111 xxx xxx 8642 2468 1 1111 xxxx xxxx 84 48 1 11 xx xx 11 x 10 x2 9 x2 8 x3 7 x3 6 x4 5 x 3 4 x4 3 x 3 2 x4 1 x34x3 2 x4 3 x 3 4 x4 5 x3 6 x3 7 x 2 8 x2 9 x 10 x 11 x 8448 1xxxx 19 x 1317x13 2 x 16 3 x 19 x 可以看出，秤可以看出，秤 2 克重物体的不同秤法有克重物体的不同秤法有 13 种。种。 枚举枚举每一种方案每一种方案（可用（可用 3 个符号个符号 x、y、z 分别代表不同的砝分别代表不同的砝 码，构造该问题的母函数如下）码，构造该问题的母函数如下） ： G(x) 32123 1xxxxxx 组合数学 第二章 母函数 35/49 86422468 1yyyyyyyy 8448 1zzzz （ 3 x 8 y 3 x 6 y 3 x 4 y 3 x 2 y 3 x 3 x 2 y 3 x 4 y 3 x 6 y 3 x 8 y） （ 2 x 8 y 2 x 6 y 2 x 4 y 2 x 2 y 2 x 2 x 2 y 2 x 4 y 2 x 6 y 2 x 8 y） （ 1 x 8 y 1 x 6 y 1 x 4 y 1 x 2 y 1 x 1 x 2 y 1 x 4 y 1 x 6 y 1 x 8 y） （ 8 y 6 y 4 y 2 y1 2 y 4 y 6 y 8 y） （x 8 yx 6 yx 4 yx 2 yxx 2 yx 4 y x 6 yx 8 y） （ 2 x 8 y 2 x 6 y 2 x 4 y 2 x 2 y 2 x 2 x 2 y 2 x 4 y 2 x 6 y 2 x 8 y） （ 3 x 8 y 3 x 6 y 3 x 4 y 3 x 2 y 3 x 3 x 2 y 3 x 4 y 3 x 6 y 3 x 8 y） 8448 1zzzz 3 x 8 y 2 x 8 y（ 3 x 6 y 1 x 8 y）（ 2 x 6 y 8 y） （ 3 x 4 y 1 x 6 y x 8 y）（ 2 x 4 y 6 y 2 x 8 y） （ 3 x 2 y 1 x 4 yx 6 y 3 x 8 y） （ 2 x 2 y 4 y 2 x 6 y） （ 3 xx 4 y 3 x 6 y 1 x 2 y）（ 2 x 2 y 2 x 4 y） （ 3 x 2 y 1 x x 2 y 3 x 4 y）（ 2 x 2 y1 2 x 2 y） （ 3 x 4 y 1 x 2 yx 3 x 2 y）（ 2 x 4 y 2 y 2 x） （ 3 x 6 y 1 x 4 yx 2 y 3 x） （ 2 x 6 y 4 y 2 x 2 y） 组合数学 第二章 母函数 36/49 （ 3 x 8 y 1 x 6 yx 4 y 3 x 2 y）（ 2 x 8 y 6 y 2 x 4 y） （ 1 x 8 yx 6 y 3 x 4 y）（ 8 y 2 x 6 y） （x 8 y 3 x 6 y） 2 x 8 y 3 x 8 y 8448 1zzzz 3 x 8 y 8 z （ 2 x 6 y 8 z 8 y 8 z 2 x 6 y 4 z 4 z 4 y 2 x 2 y 4 z 2 x 2 y1 2 x 2 y 2 x 6 y 4 z 4 y 4 z 2 x 2 y 4 z 8 y 8 z 2 x 6 y 8 z） （ 2 x 4 y 8 z 6 y 8 z 2 x 8 y 8 z 2 x 4 z 2 y 4 z 2 x 4 y 4 z 2 x 4 y 2 y 2 x 2 x 8 y 4 z 6 y 4 z 2 x 4 y 4 z 2 x 8 y 8 z） 3 x 8 y 8 z 例如，称例如，称 2 克的重量，有克的重量，有 13 种方法，具体称法为种方法，具体称法为（负数表示（负数表示 砝码放在左边，正数表示砝码放在右边）砝码放在左边，正数表示砝码放在右边） 2 x 11 2 y2 2 x 4 y (-1)(-1)22 2 x 4 z (-1)(-1)4 2 y 4 z (-2)4 2 x 4 y 4 z11(-2) (-2) 4 6 y 4 z222(-4) 2 x 4 y 4 z1122(-4) 2 x 4 y 8 z (-1)(-1)(-2)(-2)44 2 x 8 y 4 z (-1)(-1) 2222(-4) 6 y 8 z (-2)(-2)(-2)44 2 x 8 y 8 z 11 (-2)(-2)(-2) (-2) 44 2 x 8 y 8 z1122 22(-4)(-4) 组合数学 第二章 母函数 37/49 象下边这些称法，用上边的母函数是反映不出来的（即天平象下边这些称法，用上边的母函数是反映不出来的（即天平 两边放有同一重量的砝码，使得相同砝码抵消）两边放有同一重量的砝码，使得相同砝码抵消） 2(-1)12 (-1)(-2)122(-1)(2)14 (4)114 (4)24 (1)(1)(4)224 (2)(4)224 (1)(1)(2)(4)2224 (1)(1)(2)(2)(2)244 例例2.4.62.4.6 投掷投掷 3 个骰子，点数之和为个骰子，点数之和为 n（3n18） ，其方案，其方案 有多少种？骰子的情况如下：有多少种？骰子的情况如下： （1）3 个骰子相异；个骰子相异； （2）3 个骰子相同。个骰子相同。 解解 （1）3 个骰子不同（比如个骰子不同（比如 3 个个骰子的颜色分别骰子的颜色分别为红色、兰为红色、兰 色和黄色） ， 则问题等价于色和黄色） ， 则问题等价于 n 的每个分量值都有限制的特殊有序的每个分量值都有限制的特殊有序 3- 分拆。即分拆。即 3, 2, 1, 61 321 in nnnn i 由定理由定理 2.4.1 知，相应的母函数为知，相应的母函数为 xG 3 62 xxx 3 x 3 4 x 6 5 x 10 6 x 15 7 x 21 8 x 25 9 x 27 10 x 27 11 x 25 12 x 21 13 x 15 14 x 10 15 x 6 16 x 3 17 x 18 x 骰子的骰子的点数之和等于点数之和等于 n 的的投掷投掷方案个数就是方案个数就是 n x的系数的系数 182 n。例如点数之和等于。例如点数之和等于 15 的方案有的方案有 10 种，即种，即 组合数学 第二章 母函数 38/49 663636366654645564 546465456555 其中假设和式中的第一个加数为红色其中假设和式中的第一个加数为红色骰子的点数，后两个加数分骰子的点数，后两个加数分 别为别为兰色和黄色兰色和黄色骰子的点数，而这也恰好反映了骰子的点数，而这也恰好反映了 15 的每个分项值的每个分项值 不超过不超过 6 的全部有序的全部有序 3 分拆。分拆。 （2）3 个骰子相同，则问题等价于个骰子相同，则问题等价于 n 的特殊无序的特殊无序 3-分拆。其分拆。其 特殊性体现在对每个分量的值都限制在特殊性体现在对每个分量的值都限制在 16 之间，即之间，即 16 321 321 nnn nnnn 利用利用 Ferrers 图，此问题又可转化为求图，此问题又可转化为求 n 的最大分项等于的最大分项等于 3， 且项数不超过且项数不超过 6 的分拆数，即求方程的分拆数，即求方程 6, 1, 0, 0 321 321321 321 xxxxxx nxxx 的非负整数解的个数。相应的母函数为的非负整数解的个数。相应的母函数为 xG 2 23224325 111xxxxxxxxxxx 3 5 2 1xx 2 222324 111xxxxxxxxx 2 3 4 2 3 2 11xxxx 3 3 3 2 2 22232 1111xxxxxxxxxx 4 3 2 222 111xxxxxx 5 32 11xxx 6 3 1x 3 x 4 x 2 5 x 3 6 x 4 7 x 5 8 x 6 9 x 6 10 x 6 11 x 组合数学 第二章 母函数 39/49 6 12 x 5 13 x 4 14 x 3 15 x 2 16 x 17 x 18 x 其中点数之和等于其中点数之和等于 n 的方案数就是的方案数就是 n x 的系数（的系数（3n18） 。） 。 例如点数之和等于例如点数之和等于 10 的方案有的方案有 6 种，即种，即 106316225415324424 33 这也是这也是 10 的每个分项值不超过的每个分项值不超过 6 的无序的无序 3 分拆数。分拆数。 习习 题题 二二 1、 基本题：基本题：13，69，1315 2、 加强题：加强题：5，1011 3、 提高题：提高题：4，12，16， ， ，15 4、 关联题：关联题： 14 1. 求下列数列的母函数（求下列数列的母函数（n0,1,2，） ：，） ： （1） n n 1； （2） n5 （3） n(n1) ； （4） n(n2) （解） （解） （1） xG 0 1 n n n x n 0n n x n x 1 （2） xG 0 5 n n xn 00 41 n n n n xxn x x n n 1 4 0 1 x x n n 1 4 0 1 xx 1 4 1 1 1 x x 1 4 1 1 2 21 45 x x （3） xG 0 1 n n xnn 2 22 100 n n xnnx 0 2 12 n n xnnx 0 22 n n xx 0 22 n n xx x x x 1 2 2 3 2 1 2 x x （4） xG 0 2 n n xnn 000 121 n n n n n n xxnxnn x xx n n n n 1 1 0 1 0 2 x xx n n n n 1 1 0 1 0 2 组合数学 第二章 母函数 41/49 xx x x x 1 1 11 2 xxx 1 1 1 1 1 2 23 3 2 1 3 x xx 2. 证明序列证明序列 C(n，n)，C(n1，n)，C(n2，n)，的母函数，的母函数 为为 1 1 1 n x （证）已知集合（证）已知集合 n eeeS ， 21 的的 r-组合的母函数为组合的母函数为 0 1 1 1 r r n x r rn x 所以序列所以序列 nnC,， nnC, 1 ， nnC, 2 ，的母函数为，的母函数为 xG r x n rn x n n x n n x n n 210 21 0r r x r rn 0 11 r r x r rn 1 1 1 n x 3. 设设 S 4321 ,eeee，求序列，求序列 n a的母函数，其中的母函数，其中 an 是是 S 的满足下列条件的的满足下列条件的 n 组合数：组合数： （1） S 的每个元素都出现奇数次；的每个元素都出现奇数次； （2） S 的每个元素出现的每个元素出现 3 的倍数次；的倍数次； （3） e1不出现，不出现，e2至多出现一次；至多出现一次； （4） e1只出现只出现 1、3 或或 11 次，次，e2只出现只出现 2、4 或或 5 次；次； （5） S 的每个元素至少出现的每个元素至少出现 10 次。次。 （解） （解） （1） xG 4 53 xxx 4 2 4 1x x ； （2） xG 4 963 1 xxx 4 3 1 1 x ； 组合数学 第二章 母函数 42/49 （3） xG 2 32 11 xxxx 21 1 x x ； （4） xG 2 32542113 1 xxxxxxxxx 2 16151387653 1 2 x xxxxxxxx ； （5） xG 4 121110 xxx 4 40 1x x 。 4. 投掷两个骰子， 点数之和为投掷两个骰子， 点数之和为 r(2r12)， 其组合数是多少？， 其组合数是多少？ （解）相应的母函数为（解）相应的母函数为 xG 2 2432252 11xxxxxxxxx 6 2 5 2 4 22 3 232 111xxxxxxxxxx 12111098765432 3233322xxxxxxxxxx 其中点数之和为其中点数之和为 n 的方案数就是的方案数就是 n x的系数。的系数。 5. 居民小区组织义务活动，号召每家出一到两个居民小区组织义务活动，号召每家出一到两个人参加。设人参加。设 该小区共有该小区共有 n 个家庭，现从中选出个家庭，现从中选出 r 人，问：人，问： （1）设每个家庭都是）设每个家庭都是 3 口之家，有多少种不同的选法？当口之家，有多少种不同的选法？当 n=50 时，选法有多少种？时，选法有多少种？ （2）设）设 n 个家庭中两家有个家庭中两家有 4 口人，其余家庭都是口人，其余家庭都是 3 口人，有口人，有 多少种选法？多少种选法？ 6. 把把 n 个相同的小球放入编号为个相同的小球放入编号为 m, 21 的的 m 个盒子中， 使得个盒子中， 使得 每个盒子内的球数不小于它的编号数。已知每个盒子内的球数不小于它的编号数。已知 2 2 mm n ，求不同，求不同 的放球方法数的放球方法数 mng,。 7. 红、黄、蓝三色的球各红、黄、蓝三色的球各 8 个，从中取出个，从中取出 9 个，要求每种颜个，要求每种颜 色的球至少一个，色的球至少一个，问有多少种不同的取法？问有多少种不同的取法？ （解）设从中取（解）设从中取 r 个的不同取法有个的不同取法有 r a种，那么，数列种，那么，数列 r a的母函的母函 组合数学 第二章 母函数 43/49 数为数为 xG 3 832 xxxx 161098432 78732xxxxxxx 832 xxxx 241098543 35282163xxxxxxx 因此所求方案数为因此所求方案数为 9 a28 另法：原问题等价于从集合另法：原问题等价于从集合 S cba 888,中取出中取出 9 个元个元 素，且每个元素至少取一个。现在先把元素素，且每个元素至少取一个。现在先把元素 a、b、c 各取一个，各取一个， 然后再随意选出然后再随意选出6个， 则问题转变为从集合个， 则问题转变为从集合 1 S cba 777,中中 取出取出 6 个元素，且每个元素个数不限，求重复组合的方案数。又个元素，且每个元素个数不限，求重复组合的方案数。又 由于每个元素的个数大于由于每个元素的个数大于 6，故从，故从 1 S中取中取 6 个元素与从集合个元素与从集合 2 S cba ,中取出中取出 6 个元个元素的组合数一样多，从而知不同的素的组合数一样多，从而知不同的 取法为取法为 28 2 8 6 163 CC 8. 将币值为将币值为 2 角的人民币，兑换成硬币（壹分、贰分和伍分）角的人民币，兑换成硬币（壹分、贰分和伍分） 可有多少种兑换方法？可有多少种兑换方法？ （解）这是求正整数（解）这是求正整数 n 的分项只能等于的分项只能等于 1