1 1 1 x5 1 x 2 5 1 x 1 x 1 x
1 1 x 2
n 1x n
n 0

sfsf
16
2.1母函数
例 从n双互不相同的袜子（每双袜子中的两只相同）中取出r只， 要求没有任何两只是成对的，共有多少种不同的取法？
解：生成函数为: G( x ) (1 x )
sfsf
13
2.1母函数
例 求不定方程k1+k2+k3+k4=20的解数。其中, 限制k1可取0,2,4; k2可取1,3,5; k3可取6,7;k4可取8,9。 G(x)=(1+x2+x4)(x+x3+x5)(x6+x7)(x8+x9)
= (1+x2+x4) (1+x2+x4)x(1+x)x6(1+x)x8
例 确定苹果、香蕉、橘子和梨的n-组合的个数，其中在每个n组合中要求：苹果的个数必须是偶数，香蕉的个数必须是5的倍 数，橘子的个数最多4个，梨的个数为0或1个。 解：生成函数为:
G( x) (1 x 2 x 4 ....)(x 0 x 5 ....)(1 x x 2 x 3 x 4 )(1 x)
sfsf
12
2.1母函数
例 求不定方程k1+k2+k3+k4=20的解数。其中, 限制k1可取0,2,4; k2可取1,3,5; k3可取6,7;k4可取8,9。
解：设不定方程k1+k2+k3+k4=k的解组数目为ck，本例中m=4, k=20。 注意到对ki(i=1,2,3,4)的限制，序列{ck}对应的生成函数为: G(x)=(1+x2+x4)(x+x3+x5)(x6+x7)(x8+x9)
母函数及其应用
sfsf
1
排列组合问题
sfsf
2
2.1母函数
定义2.1.1 对于数列{an}，称无穷级数
G x an x n
n 0
为该数列的（普通型）母函数，简称普母函数或母函数。同时称 {an}为G(x)的生成数列。 例 有限数列C(n,r)，r＝0,1,2, …,n的普母函数是
n
sfsf
4
2.1母函数
sfs数
sfsf
7
2.1母函数
sfsf
8
2.1母函数
sfsf
9
2.1母函数
sfsf
10
2.1母函数
例 设有2个红球，1个黑球，1个白球，问 （1）共有多少种不同的选取方法，试加以枚举？ （2）若每次从中任取3个，有多少种不同的取法？ 解：设想用x，y，z分别代表红、黑、白三种球，两个红球的取 法与x0，x1，x2对应起来，即红球的可能取法与1＋x＋x2中x的 各次幂一一对应，亦即x0＝1表示不取，x表示取1个红球，x2表 示取两个。对其它球，依此类推。则母函数 G(x,y,z) ＝(1＋x＋x2) (1＋y) (1＋z) ＝1＋(x＋y＋z)＋(x2＋xy＋xz＋yz)＋(x2y＋x2z＋xyz)＋( x2yz) 若令x＝y＝z＝1，就得所有不同的选取方案总数为 G(1,1,1) ＝1＋3＋4＋3＋1＝12
g ( x) (1 x x ....)( 1 x x ...)
3 6 4 8
(1 x 2 x 4 ....)( 1 x 5 x10 ...) 1 1 1 1 3 2 4 5 1 x 1 x 1 x 1 x
sfsf
15
2.1母函数
sfsf 11
2.1母函数
例 设有2个红球，1个黑球，1个白球，问 （1）共有多少种不同的选取方法，试加以枚举？ （2）若每次从中任取3个，有多少种不同的取法？ 解：若只考虑每次取3个的方案数，而不需枚举，则令y＝x，z ＝x，便有 G(x) ＝ (1＋x＋x2) (1＋x) (1＋x) ＝ 1＋3x＋4 x2＋3 x3＋ x4 由x3的系数即得所求方案数为3。
n
r C n , r x n 0
例 从n双互不相同的五指袜子中取出r只，要求没有任何两只是 成对的，共有多少种不同的取法？
r r C n , r 2 x 解：生成函数为: G( x ) (1 2 x)
n
n 0
sfsf
17
2.1母函数
例 某班有甲乙丙三个小组，人数分别为5，6，9。把5本相同的 书分给甲、乙、丙3个小组，再发到个人手上，每人最多发一本。 考虑将分给某组的某本书发给该组的同学A与将其发给同学B被 认为是不同的分法（每个同学最多一本），而且甲、乙两组最 少1本，甲组最多5本，乙组最多6本，丙组最少2本，最多9本， 问有多少种不同的分配方案？ 解：
= (1+x2+x4)2(1+x)2x15 = (1 +x +x2 +x3 +x4 +x5)2x15 只需要多项式(1 +x +x2 +x3 +x4 +x5)2展开式中x5的系数就等于x20 的系数，由多项式定理：C20=6.
sfsf
14
2.1母函数
例 求不定方程3k1+4k2+2k3+5k4=n的非负整数解的个数。
5 6 9 4 5 6 9 5 6 9 5 6 9 5 1 1 2 x 1 1 3 1 2 2 2 1 2 x 5 6 9 20 5 6 9 x
0 1 2 2 n n Cn Cn x Cn x Cn x 1 x n
sfsf
3
2.1母函数
例 无限数列{1，1，…，1，…}的普母函数是
1 x x x
2
2
n
1 1 x
例 无限数列{1，2，…，n，…}的普母函数是
1 1 2 x 3 x (n 1) x 2 (1 x )
sfsf
18
2.1母函数
5 5 i 6 6 i 9 9 i G( x ) x x i x i i i 1 i 1 i 2