g(x)(1x2x4...x)(x3.. .)
(1 x.. .x4)x (x2...)
11x21xx211xx51xx
x2(1x5) (1x2)2(1x)2
x 2 2 x 3 5 x 4 8 x 5 1 x 6 1 4 x 7 2 9 x 8 .8 .
所 h 2 以 1 ,h 3 2 ,h 4 5 ,h 5 8 ,......
§5 生成函数求解组合问题
例1 g ( x ) ( 1 x . x . 5 ) 1 . x ( x 2 ) 1 x ( . x . 4 ) . 是什么数列的生成函数？
解 展开式的一 xr1x般 r2xr3项 xn为 ,其中
r1r2r3n, 0r15,0r22,0r34 xn的系hn数 恰为上述方程 数的 解非 的.负 个 所以g(， x)是上述方程的非的 负个 整 h数 n数解 的生成函数。
1!32!!21!!1 !2!
（4）考虑指数生成函数
若 r令 2x2,g2x2,
则r2g2x2
x2
4!
x4
2!
2!
2! 2! 2!2! 4!
x4的 系 数 恰 r2g2的 为排 组列 合数 。
4! 令
r g b x , r2 g 2 b 2 x 2, r3 g 3 b 3 x 3
1 !
2 !
例1 常函 h n 数 1, G e(x)11 x !x 2!2...x n n !...ex
例2 排列数： P n 0,P n 1,P n 2, ,P n n
G e(x ) P n 0 P n 11 x ! P n 2x 2 ! 2 . .P .n nx n n ! (1 x )n
例3 等比数列： 1,a1,a2,a3,
例2 S ={2a, b,2c }, 求S 的所有n 组合数。 解 设n组 合 数 hn,为hn的 生 成 函 数 为
G(x)(1xx2)(1x)(1xx2) 13x5x2 5x3 3x4 x5
S 的1组合数=3：a, b, c S 的2组合数=5：2a, 2c, ab, ac, bc S 的3组合数=5：2ab, 2ac, b2c, a2c, abc S 的4组合数=3：2a2c, 2abc, ab2c S 的5组合数=1：2ab2c
x7
x8
x9
x10
1785140 765012600
7!
8!
9!
1!0
p5215
例3 用1,3,5,7,9 组成一个n 位数，要求3,7出 现偶数次。共有多少个这样的n 位数？
解 可以把重复数取为无穷。
Ge(x)11x!
x2 2!
3 1
x2 2!
x4 4!
2
e3x
ex
ex 2
2
1 4
e5x
S的r排列数pr为 ,其指数生成函数为
Ge(x)11x!x2!2xn1n!1 11x!x2!2xn2n2!
xr的 r!
11x!x2!2 xnknk! 系数 S的 即 r排为 列pr。 数
例1 S ={2a,b,2c}, 求S 的所有 r 排列数
解
令 G e(x ) 11 x !x 2 ! 2 e(x ) 1 a 11 x ! a 2x 2 ! 2 .. a .nx n n ! eax
三、多重集的排列
设 S n 1 a 1 ,n 2 a 2 , ,n k a k ,考 S 的 r 排 虑 列
先考虑一个特殊问题： S 3 r,2 g ,3 b ,
即3个红球、2个绿球、3个兰球的各种排列。 （1）求出所有组合：
1 3 n 2 n 1x n 3 n 2 n 1x n
2n 0 2 n ! n 1 2 n !
p 0 0 ,p n 3 n 2 2 n 1 , n 1 ,2 ,3 ,
习题（第4版）P182
29，30（3，6），31，36，37， 42，43，45
设 S的 r组合cr数 ,则 c0为 ,c1,c2,,c8的生成函数
G ( x ) 1 x x 2 x 31 x x 21 x x 2 x 3
1 3 x 6 x 2 9 x 3 1 x 4 0 9 x 5 6 x 6 3 x 7 x 8
根x据 4的 系,数 S的 4可 组知 合 1种 共 0 。 有
1 1x21 1x51 1 x x 5(1x)
(1
1 x)2
Cn n1xn (n1)xn
n0
n0
所h n 以 n1
例4 用n个水果组成一只个果篮。果篮中可以装 4种水果：苹果为偶数，香蕉为奇数，至多 有4个桔子，至少有一个西瓜。可以有多少 种装法？
解 设共h有 n 种装法 生。 成函数为
10x2 10x3 5x4 x5
设cn 表示满足要求的n男组 女合数。生成函数为 C(x) A(x)B(x)
10x2 10x3 285x4 281x5 840x6 728x7 630x8 350x9 150x10 38x115x12 x13
4人小组的数x4目 的为 系2数8。 5 组合为2男 ：2女4， 女， 组合数恰C为 82C52 C80C54 285
（2）求出具体的组合成分 —— 三元展开式：
1rr2r3 1gg2 1bb2b3 所有2组合
1(rgb)(r2 g2 b2 rgrbgb) 所有3组合
(r3 r2grg2 r2brgbg2brb2 gb2 b3)
(rb3 gb3 r2b2 rbg2 b2g2 r3gr2gbrg2b
r3br2b2)
例5 某单位有8男5女，从中选出一个小组。要 求男士为偶数，女士至少2人，有多少种组 合方式？
解 请注意：每个人是有区别的！
设an 表示从8男士中选出偶数的数组。合 A(x) C80 C82x2 C84x4 C86x6 C88x8
128x2 70x4 28x6 x8
设bn 表 示5从 女 士 中 至 少 2人选 的出 组 合 数 B(x)(1x)5 15x
2e3x
ex
14
n0
5n
xn n!
2 3n
n0
xn n!
n0
xn n!
1
5n 23n 1 xn
4 n0
n!
p n1 45n23n1
例4 用红、白、蓝给 1xn 棋盘着色，要求红格 必须为偶数。共有多少种着色方法？
解 可以把重复数取为无穷。
Ge(x)11x!
x2 2!
2 1
x2 2!
满足要求的所有 为组合数 101028528138513328
例7
hn是方3程 r14r22r35r4 n
的非负整数解 求h的 n的个生数成，函数
解 g (x )(1x 3x 6...(1 )x 4x 8...)
(1x 2x 4...(1 )x 5x 1 0...)
1111 1 x 31 x 41 x 21 x 5, x 1
13x4x23x35x41x5 44
x x 2
x 3 5 x 4 1 x 5
1 3 1 !4 2 ! 3 3 ! 4 ! 5 !
1 ! 2 ! 3 ! 4 4 ! 4 5 !
p131!3, p242!8, p333!18, p430, p530
例2 用1,2,3,4 组成一个五位数，
1出现至少一次，至多两次； 2出现不超过1次； 3出现的最多3次； 4出现的次数必须是偶数 这样的五位数共有多少个？
解 令 G e (x ) 1 x ! x 2 ! 2 1 1 x ! 1 1 x ! x 2 ! 2 x 3 ! 3 1 x 2 ! 2 x 4 ! 4
x x2
x3
x4
x5
x6
5 18 64 215 645
1! 2! 3! 4!
5!
6!
例3 用n个水果组成一只个果篮。果篮中可以装 4种水果：苹果为偶数，香蕉为5 的倍数， 至多有4个桔子，至多有一个西瓜。可以有 多少种装法？
解 设共有 hn 种装法h。 n是方程
r1 r2 r3 r4 n
的非负整数解的其 个生 数成 。函数为
g ( x ) ( 1 x 2 .1 . x 5 . .( ) . x 1 ( . . ) x . 4 ) 1 . x ( )
Cn11!1x!Cn22!x2!2
Cnnn!
xn n!
Pn0
Pn1
1x!Pn2
x2 2!
Pnn
xn n!
xk k!
的系数恰好Pn对 k 应
二、指数生成函数
对 给 定 的h数 0,h1列 ,h2,
x x2
xn
Ge(x)h0 h1 1!h2
2! hn
n!
称 为 {hn}的 指 数 生 成 函 数 。
3 !
前式中的4次项化为：
34!44!3 4!x4 2!2!1!3!1!1!24!!
G e (x ) 1 1 x ! x 2 ! 2 x 3 ! 3 1 1 x ! x 2 ! 2 1 1 x ! x 2 ! 2 x 3 ! 3
x 2 x 3 x 4
8 ! x 8
x4 4!
e2x
ex
ex 2
12
e3x
ex
3n 1 xn
n0 2 n!
3n1 pn 2
例5 用红、白、蓝给 1xn 棋盘着色，要求红格 必须为偶数，至少有一个蓝格。
共有多少种着色方法？
解
Ge(x)1x2!2x4!411x!x2!21x!x2!2
ex2exex
ex11e3xe2xex1 2
(1x25 x50 x7)51 (x5)0
1 1 x1 1 x 51 1 x 11 1 0 x x 1 20 ( 5 1 0 x 5)0
§6 用指数生成函数求解排列问题
一、问题的提出