《组合数学》教案 2章(母函数)

1. 普母函数及其在组合问题中的应用

2. 指母函数及其在排列问题中的应用

新方法：母函数方法。

表2.0.1

2.1   母函数

（一） 母函数

（1）定义

【定义2.1.1】对于数列，称无穷级数为该数列的（普通型）母函数，简称普母函数或母函数。

（2）例

【例2.1.1】有限数列（r＝0, 1, 2, …, n）的普母函数是：

＝＝

【例2.1.2】无限数列{1, 1. …, 1, …}的普母函数是

＝＝

（3）说明 

●可以为有限个或无限个。

● 数列与母函数一一对应。

{0, 1, 1, …, 1, …}＝

● 将母函数视为形式函数，目的是利用其有关运算性质完成计数问题，故不考虑“收敛问题”，而且始终认为它是可“逐项微分”和“逐项积分”的。

（4）常用母函数

（1）组合的母函数

【定理2.1.1】组合的母函数：设,且n1＋n2＋…＋nm＝n，则S的r可重组合的母函数为

＝＝

其中，r可重组合数为之系数，r＝0, 1, 2, …, n。

理论依据：多项式的任何一项与组合结果一一对应。

优点：

●将无重组合与重复组合统一起来处理；

●使处理可重组合的枚举问题变得非常简单。

（2）特例

【推论1】，则r无重组合的母函数为

G(x)＝ (1＋x)n

组合数为之系数。

【推论2】，则r无限可重组合的母函数为

G(x)＝

组合数为之系数。

【推论3】，每个元素至少选一个：

母函数     G(x)＝

组合数     

【推论4】，每个元素选非负偶数个：

母函数   G(x)＝＝

组合数   ＝。

【推论5】，每个元素选奇数个：

母函数  G(x)＝＝

组合数  

【推论6】S＝，且n1＋n2＋…＋nm＝n，元素至少出现次：为

母函数  G(x)＝＝

组合数  

r＝k, k＋1, …, n，k＝k1＋k2＋…＋km。

（3）一般情形：设S＝{20.a，30.b，∞.c}，并设元素a只能出现1～5，10，13，16次，b只允许出现奇数次，c至少出现5次且必须出现偶数次，求S的r可重组合的母函数。

G(x)＝

（三） 应用

【例2.1.3】设有2个红球，1个黑球，1个白球，问

（1）共有多少种不同的选取方法，试加以枚举？

（2）若每次从中任取3个，有多少种不同的取法？

（解）（1）元素符号化（x，y，z红、黑、白球），元素的个数以符号的指数区分。母函数

G(x, y, z) ＝(1＋x＋x2) (1＋y) (1＋z)

＝1＋(x＋y＋z)＋(x2＋xy＋xz＋yz)＋(x2y＋x2z＋xyz)＋( x2yz)

5种情况：

1数字1表示一个球也不取的情况，共有1种方案；

2取1个球的方案有3种，即红、黑、白三种球只取1个；

3取2个球的方案有4种，即2红、1红1黑、1红1白、1黑1白；

4取3个球的方案有3种，即2红1黑、2红1白、三色球各一；

5取4个球的方案有1种，即全取。

令x＝y＝z＝1，得方案总数

G(1,1,1) ＝1＋3＋4＋3＋1＝12

（2）只考虑每次取3个的方案数，不需枚举

令y＝x，z＝x

G(x)＝(1＋x＋x2) (1＋x) (1＋x)＝1＋3x＋4 x2＋3 x3＋x4

由x3的系数即得所求方案数为3。

【例2.1.4】有18张戏票分给甲、乙、丙、丁4个班（不考虑座位号），其中甲、乙两班最少1张，甲班最多5张，乙班最多6张，丙班最少2张，最多7张，丁班最少4张，最多10张，问有多少种不同的分配方案？

（解）（1）分析：实质为甲、乙、丙、丁四类共28个元素中可重复地取18个元素的组合问题。，m＝4，n＝n1＋n2＋n3＋n4＝5＋6＋7＋10＝28，k＝＝ 1＋1＋2＋4＝8，r＝18。

（2）求解：母函数

G(x)＝

＝x8＋…＋140 x18＋…＋x28

（3）特殊情况处理：戏票数r＝4，＝0（i＝1, 2, 3, 4）

G1(x)＝

＝

G2(x)＝＝

＝

系数相同，用G2(x)计算要比用G1(x)方便得多（因为将扩展为不影响的系数）

同理，r＝6，可用

G3(x)＝＝

代替G1(x)求的系数。

【例2.1.5】从n双互相不同的鞋中取出r只（），要求其中没有任何两只是成对的，问共有多少种不同的取法？

（解）解法一：母函数法。视为，但同类中的两个不一样，即

故其r重组合的母函数为

G(x)＝(1＋2x)n＝

不同的取法共有种。

本质：每类元素最多只能出现一次，但同类元素互换后方案不同。故G(x)＝中不能有项，再由同双的两只鞋子有区别知，x的系数应为2。

解法二：排列组合。先从n双鞋中选取r双，共有种选法，再从此r双中每双抽取一只，有种取法。

解法三：排列组合。先取出k只左脚的鞋，再在其余双鞋中取出只右脚的鞋：

＝

得组合恒等式

＝

一般提法：

S＝

从中取出r个，第类元素最少个，最多个，母函数：

G(x)＝ 

举例， 把5本相同的书分给甲、乙、丙3个班，再发到个人手上，每人最多发一本。考虑将分给某班的某本书发给该班的同学A与将其发给同学B被认为是不同的分法，而且甲、乙两班最少1本，甲班最多5本，乙班最多6本，丙班最少2本，最多9本，问有多少种不同的分配方案？

S＝，，n＝＝5＋6＋9＝20，k＝＝1＋1＋2＝4，r＝5。母函数

G(x)＝

＝

＋＋…

＋

＝1080＋7380＋…＋

共有7380种分配方案。

说明：与问题“从20个相异元素中不重复地抽取5个元素” 不等价（答案为＝15,504）。

【例2.1.6】甲、乙、丙3人把n（n≥3）本相同的书搬到办公室，要求甲和乙搬的本数一样多，问共有多少种分配的方法？

（解）（1）分析：组合问题：从集合中可重复地选取n个元素，要求与的个数一样多，求不同的选取方案数。

特点：盒子之间的关系。

（2）特例：n＝1，1种分法，甲和乙都分0本（丙1本）。

n＝2，2种分法：甲和乙分0本（丙2本）或甲和乙1本（丙0本）。当n＝3时，分法2种。

当n＝4或5，3种分法：甲和乙都分0本、1本或2本。

（3）一般情形：视为2个大盒子A、B，且A又分为2个小盒子。分两步分配：

第一步：A盒子分偶数本，B盒子分任意本；

第二步：将分给A盒的书再给甲、乙各分一半。

＝

＝

＝＋＋

＝

＝

不同的分配方法共有种。

——上整数函数。即不小于x的最小整数。

（待定系数法：分解有理多项式：

＝

＝＋＋

＝

＝，

比较同次幂系数得方程组，

解之得A＝B＝1/4，C＝1/2）

【例2.1.7】证明组合等式

（1）＝

（2）＝

（3）＝，   n≥m

（证）（1）二项式 

＝

两端求导

＝   （*）

令x＝1即可。

（2）（*）式两端同乘以x后求导

＝

令x＝1。

（3）   ＝

两边展开

•

＝ 

比较两边的常数项。

2.2   母函数的性质

母函数与生成数列一一对应若两个母函数之间存在某种关系，则对应的生成数列之间也必然存在相应的关系。反之亦然。

设：数列{a k}、{b k}、{c k}的母函数分别为A(x)、B(x)、C(x)，且都可逐项微分和积分。

【性质1】若（即），则B(x)＝。

（证）B(x)＝ 

＝＋ 

＝ 

＝

分析：向右移r个位置且前面补0

＝

 【性质2】若，则

B(x)＝

（证）B(x)＝b0＋b1 x＋b2 x 2＋…＝ar＋ar＋1 x ＋ar＋2x 2＋…

＝( ar x r＋ar＋1 x r＋1 ＋ar＋2x r＋2＋…)

＝

分析：向左移r个位置且前面舍掉

＝

 【性质3】若，则B(x)＝。

（证）等式两端乘以对k求和：

k＝0: 

k＝1: 

k＝2: 

k＝n: 

＋)

即 B(x)＝

＝

＝

＝

＝

例，已知

A(x)＝1＋x＋x 2＋…＋x n＋…＝，（＝1）

令＝k＋1

B(x)＝1＋2x＋3x 2＋…＝＝＝

或   B(x)＝

同理，令ck＝＝1＋2＋…＋(k＋1)，可得

C(x)＝1＋3x＋6x 2＋10x3＋15x 4＋…

＝＝

C(x)＝B(x)A(x)＝(1＋2x＋3x 2＋…)( 1＋x＋x 2＋…)＝

类推：

D(x)＝C(x) A(x)＝(1＋3x＋6x 2＋10x3＋…)( 1＋x＋x 2＋…)

＝＝

【性质4】若收敛，且b k＝，则

B(x)＝

（证）首先由条件知b k存在，按定义

b0＝a0＋a1＋a2＋…＝A(1) 

b1＝a1＋a2＋a3＋…＝A(1)－a0

……

bk＝ak＋ak＋1＋ak＋2＋…＝A(1)－a0－a1－a2－…－ak-1

……

给bk对应的等式两端都乘以xk并分别按左右求和，得

左端＝＝B(x) 

右端＝A(1)＋x＋x 2＋x 3＋…

＝A(1)[1＋x＋x 2＋…]－a0x[1＋x＋x 2＋…]－a1x 2 [ 1＋x＋x 2＋…]－…

＝－

＝－＝

【性质5】若bk＝kak，则B(x)＝xA'(x) 。

（证）B(x) ＝＝＝

＝＝

＝x[A(x) －a0] '＝xA'(x)

【性质6】若b k＝，则B(x)＝

（证）B(x) ＝＝＝

＝＝

 【性质7】若c k＝，则C(x)＝A(x) B(x) 。

（证）  c0＝a0b0

c1＝a0b1＋a1b0

c2＝a0b2＋a1b1＋a2b0

cn＝a0bn＋a1bn-1＋…＋anb0

给ck对应的等式两端都乘以xk后左右两边分别求和，得

C(x)＝a0b0＋(a0b1＋a1b0)x＋(a0b2＋a1b1＋a2b0)x2＋…＋(a0bn＋a1bn-1＋…＋anb0)xn＋…

＝a0 (b0＋b1x＋b2 x2＋…)＋a1x(b0＋b1x＋b2 x2＋…)＋a2x2 (b0＋b1x＋b2 x2＋…)＋…

＝(a0＋a1x＋a2 x2＋…) (b0＋b1x＋b2 x2＋…)

＝A(x) B(x)

2.3   指数型母函数

回顾：普通型母函数较好地解决了各种组合的计数问题。

分析：组合数数列的母函数在解决计数问题和证明组合恒等式时之有用的原因：具有有限封闭形式。

启发：对排列问题也采用母函数方式。尤其是n个不尽相异元素中取r个的排列问题。

困难：对于排列数数列{ P(n，r) }，采用普通型母函数十分不便。原因：它不能表为初等函数形式。

改进：n集的r无重排列数和r无重组合数之间的关系：

C(n，r) ＝

 (1＋x)n＝＝

总结：在(1＋x)n的展开式中，项的系数恰好是排列数。启发：排列数数列的母函数为。

（一） 数列的指母函数

（1）定义

【定义2.3.1】对于数列{}≡{ a 0，a 1，a 2，…}，把形式幂级数

≡a 0＋a1＋a2＋…＋an＋…

称为数列{ a k }的指数型母函数，简称为指母函数，而数列{ a k }则称为指母函数的生成序列。

（2）例

1．{＝1 }，Ge(x) ＝＝。

2．{＝}，Ge(x)＝＝(1＋x)n

（3）说明

1．可以为有限个或无限个；

2．数列指母函数。例

{0,1,1,…,1,…}＝

3．将母函数视为形式函数，且始终是收敛的。

4．同一数列数列{}，一般G(x)≠Ge(x)。

例 {＝1 }的普母函数为G(x)＝，指母函数为Ge(x)＝。

例外：当＝0时（k≥2），

G(x)＝＝＝Ge(x)

5．对同一函数，令

f(x)＝Ge(x)＝

或                 f(x)＝G(x)＝

则一般。例外＝。

＝

视＝G(x)为普母函数，则

＝

视＝Ge(x)为指母函数，则

＝

（二） 排列问题

【定理2.3.1】设重集,且n1＋n2＋…＋nm＝n，则S的r可重排列的指母函数为

Ge(x)＝＝

其中，r可重排列数为之系数，r＝0,1,2, …,n 。

【例2.3.1】盒中有3个红球，2个黄球，3个篮球，从中取4个球，排成一列，问共有多少种不同排列方案？

（解）m＝3，＝3，＝2，＝3，r＝4 

＝

＝1＋3x＋＋＋＋＋＋＋

＝1＋3＋＋26＋＋＋＋＋

取4个球的排列方案数为70。

枚举：令

Ge(r,y,b)＝

Ge(r,y,b)＝1＋

＋

＋(＋＋＋＋＋)

＋…＋

详细枚举：取1个球的3种排列方案为红、黄、蓝各分别取1个。取2个球的9种排列方案为：红红、黄黄、蓝蓝、红黄、黄红、红蓝、蓝红、黄蓝、蓝黄。

说明：（1）利用普母函数能枚举到每一种组合情况，但指母函数做不到，只能对排列进行分类枚举。

（2）一个问题的普目函数和指目函数可以互相转换。

例：在令每一项系数为1，即得普母函数。

（3）已知问题的普母函数，可利用其生成指母函数。

（三） 特例

【推论1】 

指母函数  ＝

排列数为之系数。

【推论2】

指母函数  

排列数为  nr

【特例】每个元素至少选一个（即r≥n）

＝＝

＝

方案数  。

【推论3】，ei至少取ki个（ki≥0）

指母函数  

【推论4】，r＝n，全排列数

（四） 应用

 【例2.3.2】五个数字1，1，2，2，3能组成多少个四位数？

（解）用表示组成r位数的个数，{}的指母函数为

＝

＝1＋3＋8＋18＋30＋30

能组成30个四位数。

【例2.3.3】求1，3，5，7，9五个数字组成的n位数的个数（每个数字可重复出现），要求其中3，7出现的次数为偶数，1，5，9出现的次数不加。

（解）设满足条件的n位数的个数为，指母函数：

＝

＝

＝

＝

∴   

【例2.3.4】把上例的条件改为要求1、3、7出现的次数一样多，5和9出现的次数不加。求这样的n位数的个数。

（解）设满足条件的数有个，类似例2.1.6

Ge(x)＝

＝

＝

＝

＋

＋

＝

即：＝1，＝2，＝4，＝14，＝，＝272，＝1114

一般情形，当n＝时

理解（按排列）： 

【例2.3.5】在例2.1.5中，若把所取出的r 只鞋再排成一列，问共有多少种结果？

（解）即从集合的n类共2n个元素中不重复地取出r个元素排成一列，且同一类元素，不能同时出现（1≤i≤n）。指母函数：

＝＝＝

不同的排列数为＝。

与例2.1.5类似，本问题的排列数也可以从排列的角度理解为：先从n双鞋子中不重复地选出r双排成一列，共有种排列情况，再从所选的每双鞋中抽取一只，有种取法。由乘法原理，即得所求结果。

分配问题：将r个不同的球放入n个不同的盒子，每个盒子最多放一个球，而且每个盒子中有两个相异的格子，故还需要进行二次分配。如果某个盒子中放进一个球，那么，二次分配时有两种可选的方案。

一般提法：集合S中有m类元素，第i类元素有个，且同一类元素也互不相同，从S中取出r个元素排成一列，问共有多少种排列结果？其中要求第i类元素最少，最多个，则此排列问题的指母函数为

＝＝

即得问题的答案（r＝0，1，…，n）。

2.4   正整数的分拆

问题：将一个正整数分拆成若干个正整数之和。

关联问题：分配问题、一次方程整数解的个数问题。

（一） 概念

【定义2.4.1】

称该分解是n的一个k分拆，并称为分量（或分项）。

（二） 分类

●有序分拆 考虑间的顺序。

例   5＝2＋1＋1＋1＝1＋2＋1＋1

●无序分拆 不考虑顺序（可把分项按大小排序）。

例   5＝2＋1＋1＋1＝3＋2＝3＋1＋1

2.4.1 有序分拆

求n的k有序分拆的个数求一次不定方程全体正整数解的组数。

可对每个分量加以条件：1≤≤（＝1, 2, …, k）。

【定理2.4.1】n的k有序分拆

分拆数列的母函数：

…

组合意义（分配问题）：把n个相同的球放入k个不同的盒子里，第个盒的容量为（＝1,2, …,k），且使每盒非空。

【推论】若对n的k有序分拆的各分量没有，则其k有序分拆数列的母函数是，且＝。

2.4.2 无序分拆

（三） 问题

简称分拆，分拆数记作，称为最大分项。

问题转换：将n分拆为k项（每一项的大小不受）的分拆数等于将n分拆为最大分项为k（分项个数不限）的分拆数。

设满足后一种条件的k分拆数也为。

（四） 最大分项＝k的分拆

分拆数＝不定方程整数解的组数

即整数n由1，2，…，k允许重复且k至少出现一次的所有组合数。母函数：

…

＝＝

（五） 最大分项≤k的分拆

分拆数＝不定方程整数解的组数

分拆数列的母函数：

…

＝＝

2.4.3 Ferrers图

（六） 定义

一个从上而下的k层格子，设为第层的格子数，当≥（＝1，2，…，n-1），即上层的格子数不少于下层的格子数时，称为Ferrers图。

（七） 性质

（1）每一层至少有一个格子

（2）Ferrers图与无序分拆

对应关系：第1层的格子数对应分项，第2层的格子数对应分项，…。

图（a）20＝7＋5＋5＋2＋1

（3）“转置”的图仍为Ferrers图，称为原Ferrers图的共轭图，或者说这两个图是一对共轭的Ferrers图。若某个Ferrers图与其共轭图形状相同，则称其是自共轭的。

共轭图对应的分拆叫做共轭分拆

图（b）共轭分拆20＝5＋4＋3＋3＋3＋1＋1

（八） 应用

【定理2.4.2】

（1）n的所有k分拆的个数等于把n分拆成最大分项等于k的所有分拆数；

（2）把n分拆成最多不超过k个数之和的分拆数等于把n分拆成最大分项不超过k的所有分拆数。

（证）两种分拆一一对应关系。

【推论】正整数n分拆成互不相同的若干个奇数的和的分拆数，与n分拆成有自共轭的Ferrers图的分拆数相等。

（证）建立一一对应关系。设

， 

Ferrers图特点：第i行、第i列元素为个；是自共轭的。反之亦然。

17＝9＋5＋3

令 p(n)＝n的全部无序分拆数（称作n的分拆数）

【定理2.4.3】正整数n的全部分拆总数数列的母函数是

＝

当n较大时，计算p(n)是非常困难的。

p(1)＝1，  p(5)＝7，  p(10)＝42， 

p(15)＝176， p(20)＝627，  p(25)＝1958，  

p(200)＝3972999029388≈4万亿

p(n)的渐进公式和估值不等式：

【例2.4.4】关于的计算，有

（1）

（2）

（3），n＞2.

利用二元递归函数计算p(n)的算法：

【定理2.4.5】令＝正整数n的最大分项n1≤m的所有分拆数：

实质上是函数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，而其它的分拆都是n1≤n-1；

(4)N的最大分项为m的分拆数分为两部分：①以m作为第一分项，其余分项之和等于n－m，且最大分项n2不超过m的分拆数Q(n-m,m)；②最大分项n1≤m-1的分拆数Q (n，m-1)。

2.4.5应用

【例2.4.1】（各分项不同，即不重复）设有1克、2克、3克、4克的砝码各一枚，若要求各砝码只能放在天平的一边。问能称出那几种重量？有哪几种可能方案？

（解）典型的正整数分拆问题。

例：6克物品＝3＋2＋1＝4＋2

分拆条件：最大分项不超过4时，6的无序不重复分拆有两种

一般条件：将整数n分拆为最大分项不超过4，且各分项最多只能出现一次的分拆。

母函数： 

 ＝

结论：可称出从1克到10克共10种重量，幂的系数即为称出n克重量的方案数。

枚举：分拆数的母函数：

＝1＋x＋y2＋(xy2＋z3)＋(xz3＋w4)＋＋＋＋＋y2z3w4＋xy2z3w4

规律：若（＝0或）中各因子的指数之和为n，则单项式对应一种称n克重量的方案。

例：对应称7克重量的方案之一，而且用的是3克和4克的砝码。另一方案为xy2w4对应的用1克、2克和4克的砝码。

说明：

a)取1＋2＋3＝2＋4，重量相同，元素个数不同，对应所取元素个数不同的组合方案。

b)若取两个元素，如2＋3＝5，3＋4＝7，元素个数相同，但重量不同，是不同的整数的分拆方案。

c)组合关心的是元素的个数，分拆关心的是元素的加权和（每个元素赋予一定的权值）。对于组合而言，其母函数应为

＝1＋(x＋y＋z＋w)＋(xy＋xz＋xw＋yz＋yw＋zw)

＋(xyz＋xyw＋xzw＋yzw)＋xyzw

【例2.4.2】（各分项无限重复）求用1分、2分、3分的邮票贴出不同面值的方案数。

（解）分项可（无限）重复的无序分拆。母函数：

G(x)＝(1＋x＋x2＋…)(1＋x2＋x4＋…)(1＋x3＋x6＋…)

＝

＝

＝

例：系数为4，贴出4分面值的方案有4种，即

4＝1＋1＋1＋1，  4＝2＋1＋1，  4＝2＋2，  4＝3＋1

说明：本题是按照邮票总面值的不同来区别并统计方案数的。若将邮票贴成一行，不同面值的邮票互换位置后算作另一种方案，则问题将成为有序分拆。

【例2.4.3】（有序分拆）在例2.4.2中，按照有序分拆，贴成总面值等于4分的方案数是多少？

（解）例：无序分拆方案4＝2＋1＋1、4＝3＋1分别对应3个和2个有序分拆方案（总的方案数为7）：

4＝2＋1＋1＝1＋2＋1＝1＋1＋2，  4＝3＋1＝1＋3

求解：利用有序分拆求方案数（分类计算）：

4的1有序分拆数为＝C(4-1，1-1)＝1，即4＝4分拆为自身；

4的2有序分拆数为＝C(4-1，2-1)＝3，即4＝3＋1＝1＋3＝2＋2；

4的3有序分拆数＝C(4-1，3-1)＝3，即4＝2＋1＋1＝1＋2＋1＝1＋1＋2；

4的4有序分拆数＝C(4-1，4-1)＝1，即4＝1＋1＋1＋1。

各项求和，即得4的全部有序分拆数为8，但本题中无4分面值的邮票，故不算，恰为7种方案。

困难性：不能一次计算到位。

【例2.4.4】（各分项有限不重复）若有1克的砝码3枚，2克的4枚，4克的2枚，问能称出多少种重量？各有几种方案？

（解）分析：无序分拆中处于不重复分拆（例2.4.1）和无限重复分拆（例2.4.2）之间的有限重复分拆问题。母函数

G(x)＝

＝1＋x＋2x2＋2x3＋3 x4＋3x5＋4x6＋4x7＋5x8＋5x9＋5x10＋5 x11＋4 x12＋4 x13＋3 x14＋3 x15＋2 x16＋2 x17＋x18＋x19

结果：共能称出19种重量

例：称8克重量（即8的分项为1、2、4的无序分拆）

8＝4＋4＝4＋2＋2＝4＋2＋1＋1＝2＋2＋2＋2＝2＋2＋2＋1＋1

扩展：若将1克的砝码改为4枚，方案增加

8＝4＋1＋1＋1＋1＝2＋2＋1＋1＋1＋1

【例2.4.5】（扩展）在例2.4.4中，若砝码可以放在天平的两边，但两边不能同时有同样重量的砝码，请给出问题的母函数。问要秤出2克重的物体，有多少种不同的秤法？并给出每一种秤法。

（解）分析：物体一边的砝码抵消了天平另一边砝码重量。

G(x)＝

＝＋＋2＋2＋3＋3＋4＋3＋4 ＋3＋4＋3＋4＋3＋4＋3＋4＋3＋3 ＋2＋2＋＋

＝＋…＋13＋17＋13＋16＋…＋

结果：秤2克重物体的不同秤法有13种。

枚举：用不同符号 x、y、z代表不同砝码：

G(x)＝ 

＝＋…

＋（＋＋＋＋＋＋1 ＋＋＋＋＋＋）

＋…＋

＋（＋＋＋＋＋ ＋＋＋＋＋＋＋）

＋…＋＋

例：称2克的重量，有13种方法（负数表示砝码放在左边，正数表示砝码放在右边）

＝1＋1

＝2

＝(-1)＋(-1)＋2＋2

＝(-1)＋(-1)＋4

＝(-2)＋4

＝1＋1＋(-2)＋(-2)＋4

＝2＋2＋2＋(-4)

＝1＋1＋2＋2＋(-4)

＝(-1)＋(-1)＋(-2)＋(-2)＋4＋4

＝(-1)＋(-1)＋2＋2＋2＋2＋(-4)

 ＝(-2)＋(-2)＋(-2)＋4＋4

＝1＋1＋(-2)＋(-2)＋(-2)＋(-2)＋4＋4

＝1＋1＋2＋2＋2＋2＋(-4)＋(-4)

反例：用上边的母函数反映不出来的称法（即天平两边放有同一重量的砝码，使得相同砝码抵消）

2＝(-1)＋1＋2

＝(-1)＋(-2)＋1＋2＋2＝(-1)＋(-2)＋1＋4

＝(-4)＋1＋1＋4

＝(-4)＋2＋4

＝(-1)＋(-1)＋(-4)＋2＋2＋4

＝(-2)＋(-4)＋2＋2＋4

＝(-1)＋(-1)＋(-2)＋(-4)＋2＋2＋2＋4

＝(-1)＋(-1)＋(-2)＋(-2)＋(-2)＋2＋4＋4

【例2.4.6】投掷3个骰子，点数之和为n（3≤n≤18），其方案有多少种？骰子的情况如下：

（1）3个骰子相异；

（2）3个骰子相同。

（解）（1）3个骰子不同（3个骰子分别为红、兰、黄色），问题等价于n的每个分项都有的特殊有序3-分拆。即

由定理2.4.1知，相应的母函数为

＝

＝＋＋25＋27

＋＋＋3

＋

骰子的点数之和等于n的投掷方案个数就是的系数。例如点数之和等于15的方案有10种，即

6＋6＋3＝6＋3＋6＝3＋6＋6＝6＋5＋4＝6＋4＋5＝5＋6＋4＝5＋4＋6＝4＋6＋5＝4＋5＋6＝5＋5＋5

原理：假设和式中的第一个加数为红色骰子的点数，后两个加数分别为兰色和黄色骰子的点数，而这也恰好反映了15的每个分项值不超过6的全部有序3分拆。

（2）3个骰子相同，问题等价于n的特殊无序3-分拆。其特殊性体现在对每个分量的值都在1～6之间，即

利用Ferrers图，问题又可转化为求n的最大分项等于3，且项数不超过6的分拆数，即求方程

的非负整数解的个数。母函数

＝

＋

＋

＋

＋

＝＋＋2＋3＋4＋5＋6＋6＋6 ＋6＋5＋4＋3＋2＋＋

其中点数之和等于n的方案数就是的系数（3≤n≤18）。例如点数之和等于10的方案有6种，即

10＝6＋3＋1＝6＋2＋2＝5＋4＋1

  ＝5＋3＋2＝4＋4＋2＝4＋3＋3

这也是10的每个分项值不超过6的无序3分拆数。

习  题  二

（1）基本题：1，3，6～9，13～15，18

（2）加强题：2，5，10～11

（3）提高题：4，12，16，17

1.求下列数列的母函数（n＝0,1,2，…）：

（1）；           （2）{ n＋5 }

（3）{ n(n－1) }  ；           （4）{ n(n＋2) }

（解）（1）＝＝＝

（2）＝＝

＝＝

＝＝

＝

（3）＝＝

＝＝

＝＝＝

（4）＝＝

＝

＝

＝

＝＝

2.证明序列C(n，n)，C(n＋1，n)，C(n＋2，n)，…的母函数为

（证）已知集合的r-组合的母函数为

所以序列，，，……的母函数为

＝

＝

＝

＝

3.设S＝，求序列的母函数，其中an是S的满足下列条件的n组合数：

（1）S的每个元素都出现奇数次；

（2）S的每个元素出现3的倍数次；

（3）e1不出现，e2至多出现一次；

（4）e1只出现1、3或11次，e2只出现2、4或5次；

（5）S的每个元素至少出现10次。

（解）（1）＝＝；

（2）＝＝；

（3）＝＝；

（4）＝

＝；

（5）＝＝。

4.投掷两个骰子，点数之和为r（2≤r≤12），其组合数是多少？

（解）相应的母函数为

＝

＝

其中点数之和为n的方案数就是的系数。

5.居民小区组织义务活动，号召每家出一到两个人参加。设该小区共有n个家庭，现从中选出r人，问：

（1）设每个家庭都是3口之家，有多少种不同的选法？当n＝50时，选法有多少种？

（2）设n个家庭中两家有4口人，其余家庭都是3口人，有多少种选法？

6.把n个相同的小球放入编号为的m个盒子中，使得每个盒子内的球数不小于它的编号数。已知，求不同的放球方法数。

7.红、黄、蓝三色的球各8个，从中取出9个，要求每种颜色的球至少一个，问有多少种不同的取法？

（解）设从中取r个的不同取法有种，那么，数列的母函数为

＝

＝

＝

因此所求方案数为

＝28

另法：原问题等价于从集合S＝中取出9个元素，且每个元素至少取一个。现在先把元素a、b、c各取一个，然后再随意选出6个，则问题转变为从集合＝中取出6个元素，且每个元素个数不限，求重复组合的方案数。又由于每个元素的个数大于6，故从中取6个元素与从集合＝中取出6个元素的组合数一样多，从而知不同的取法为

8.将币值为2角的人民币，兑换成硬币（壹分、贰分和伍分）可有多少种兑换方法？

（解）这是求正整数n的分项只能等于1、2、5的分拆数。设n的分拆数为，则的母函数为

＝

＝

＝

所以，共有＝29种兑换方法。

9.有1克重砝码2枚，2克重砝码3枚，5克重砝码3枚，要求这8个砝码只许放在天平的一端。能称几种重量的物品？有多少种不同的称法？

（解）设秤r克重的物体有种秤法，那么数列{的母函数是

展开后得

因此，能称1～22克共22种重量的物品，所有不同的称法总数为

＝3×4×4＝48

10.证明不定方程＝的正整数解组的个数为。

（证）问题可以视为将r个相同的1放入n个盒子。由于将之间的值互换，对应不同的解，所以盒子不同。设共有个解，则由式（2.1.1）知的母函数为

＝＝

＝＝

＝＝

所以

＝

11. 求方程＝24 的大于1的整数解的个数。

（解）原方程即，令，可得等价方程

由上题知后者共有＝190组正整数解，从而知原不定方程的大于1的整数解的个数为190。

12.设

an＝，bn＝

其中a0＝1，b0＝0，

（1）试证an＋1＝an＋bn＋1， bn＋1＝an＋bn；

（2）求出{ an }，{ bn }之母函数A(x)，B(x)。

（解）＝，＝

13.设S＝，求序列的母函数，其中pn是S的满足下列条件的n排列数：

（1）S的每个元素都出现奇数次；

（2）S的每个元素至少出现4次；

（3）ei至少出现i次（i＝1,2, …,k）；

（4）ei至多出现i次（i＝1,2, …,k）。

（解）（1）＝＝；

（2）＝＝；

（3）＝

＝；

（4）＝

14. 把23本书分给甲、乙、丙、丁四人，要求这四个人得到的书的数量分别不得超过9本、8本、7本、6本，问

（1）若23本书相同，有多少种不同的分法？

（2）若23本书都不相同，又有多少种不同的分法？

15. 8台计算机分给3个单位，第一个单位的分配量不超过3台，第二单位不超过4台，第三单位不超过5台，问共有几种分配方案？

（解）设分配n台计算机的分配方案有种，则的母函数为

＝

＝1＋

＋

所以分配8台计算机共有＝14种方案。

16. 用母函数证明等式

（1）。

（2）

17. 证明：自然数n分拆为互异的正整数之和的分拆数等于n分拆为奇数之和的分拆数。

（证）将n分拆为互异的正整数之和的分拆数的母函数为

＝

＝

＝

将n分拆为奇数之和的分拆数的母函数为

＝

＝＝

所以，两种分拆的方案数相同。

18. 求自然数50的分拆总数，要求分拆的每个分项不超过3。

（解）方法一  用母函数。设正整数n的分项不超过3的分拆数为，则的母函数为

＝

＝

＝

所以，50满足要求的分拆数为234种方法。

另外，可以看出，对一般的n，记

， mod 3  

则

＝

故当时，t＝16，r＝2，代入上式即得

＝

＝2＋3＋5＋6＋8＋9＋11＋12＋…＋21＋23＋24＋26

＝（1＋2＋3＋4＋…＋23＋24＋25＋26）－（1＋4＋7＋10＋…＋22＋25）

＝－＝234

方法二  利用递推公式（2.1.3）求解。这里是求。首先由公式（2.1.3）知对任何正整数n，有。其次，由递推关系＝知

＝＝1＋

直接迭代，并利用初值＝1和＝2得

＝， 

即

＝， 

最后对m＝3，有

＝＝＋

令n50，代入上式得

＝26＋＝26＋24＋＝＝

……

＝26＋24＋23＋21＋…＋12＋11＋9＋8＋6＋5＋3＋2

＝234