版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领
文档简介
第4章母函数回顾前一章——容斥原理：本章重点介绍母函数（普通母函数、指数母函数）的基本概念及其在排列组合中的应用：母函数的基本概念母函数的基本运算母函数在排列、组合中的应用整数拆分母函数在组合恒等式中的应用基本原理重集的r-组合错排、有限制排列§4.1普通母函数概念§4.1
母函数的基本概念定义4.14.1.1
普通母函数给定一无穷序列(a0,a1,…an,…)(简记为{an})，称函数
f
(
x)
=为序列{an}的普通母函数（发生、iia
x¥生成函数）i
=0。注：f(x)是无穷级数，不管其收敛性；
x为形式变元，f(x)为形式幂级数；序列与母函数一一对应；母函数是序列的另一表达形式；有限序列也可用母函数表示；可与二项式定理结合应用。§4.1
普通母函数例1§4.1
母函数的基本概念例
题4.1.1
普通母函数例
1
、
求
序
列
(C(n,0),C(n,1),C(n,2),…,C(n,n))的普通母函数。解：由定义4.1及二项式定理的推论1.9.2有0
1
nf
(
x)
=
n
+
n
x
+
...
+
n
xn=
(1
+
x)n§4.1
普通母函数例2例
题§4.1
母函数的基本概念4.1.1
普通母函数例2、求序列(C(n-1,0),-C(n,1),
C(n+1,2),…,(-1)kC(n+k-1,k),…)的普通母函数。解：由定义4.1及二项式定理的推论1.10.2有(
)(
)02kkkkx=k¥k
=0¥k
=0f
(
x)
=
n
-1
-
n
x
+
n
+1
x2
+
...
+
(-1)kn
+
k
-1
xk
+
...1n
+
k
-1k-nx
=
(1
+
x)-n=(-1)§4.1
普通母函数例3例
题§4.1
母函数的基本概念例3
、证明(1-4x)-1/2
是序列(C(0,0),
C(2,1),4.1.1
普通母函数C(4,2),…,C(2n,n),…)的普通母函数。(k
!k
!kkxkxkk
=1¥¥k
=1¥-1
2k(-4
x)-1
2
(-1
2
-1)(-1
2
-
2)...(-1
2
-
k
+1)(-4
x)k
!4k
(1·
3
·...·(2k
-1))2k
·
k
!2k
k
!(1·
3
·...·(2k
-1))¥(1
-
4
x)-1
2
=
1
+
=
1+k
=1=
1+(
)(
)
(
)(
)
(
)4
22(2k
)!0
20
1k
!k
!kkk
!k
!2k
kx(2
·4
·...·(2k
))(1·
3
·...·(2k
-1))xk2k
kk¥¥k
=1=
1
++
x
+=
1
+
k
=1=
1
+
k
=1¥k
=1x
=
1
+x
+
...
+x
+
...=证明：由牛顿二项式定理有由定义知，(1-4x)-1/2是序列(C(0,0),
C(2,1),
C(4,2),…,C(2n,n),…)的普通母函数。(kkxkxkk
!k
!k
=1¥¥¥-1
2k(-4
x)-1
2
(-1
2
-1)(-1
2
-
2)...(-1
2
-
k
+1)(-4
x)k
!4k
(1·
3
·...·(2k
-1))2k
·
k
!2k
k
!(1·
3
·...·(2k
-1))¥(1
-
4
x)-1
2
=
1
+
=
1+k
=1=
1+(
)(
)
(
)
(
)
(
)200
14
22kkx(2k
)!x2k
kkk
!k
!2k
kk¥¥¥k
=1k
=1(2
·4
·...·(2k
))(1·
3
·...·(2k
-1))k
!k
!=
1
+=+
x
+x
+
...
+x
+
...k
=1=
1
+
k
=1=
1
+
k
=1x
=
1
+
§4.1
普通母函数例4§4.1
母函数的基本概念例
题4.1.1
普通母函数例4、求序列(0,
1×2×3,
2×3×4,…,n(n+1)(n+2),…)的普通母函数。xn6
xn=0n=2n=3n=01
-
xn(n
-1)
xn-2(1
-
x)3n(n
-1)(n
-
2)
xn-3(1
-
x)4n(n
+1)(n
+
2)
xn(1
-
x)4=
0
+1·
2
·
3
x
+
2
·
3
·4
x2
+
...
+
n(n
+1)(n
+
2)
xn
+
...
1
=
¥
2
=
¥
6
=
¥ 6
x
=
¥将上式两端同时微分两次得将上式两端再微分得两边同乘以x得因此f
(x)=解：由牛顿二项式定理的推论1.10.4，有(1
-
x)4是序列(0，1·
2
·
3，2
·
3
·4,...,n(n
+1)(n
+2),...)的普通母函数。§4.1
指数母函数概念§4.1
母函数的基本概念定义4.24.1.2
指数母函数给定一无穷序列(a0,a1,…an,…)（简记为{an}），称注：fe(x)也是形式幂函数。经常可结合以下公式运算：为序列{an}的指数母函数。xii
!¥i
=0函数
fe
(
x)
=
aixnea
x
=
1
+axx22!
n!+a
2
+
...
+a
n
+
...1!x2
xnx2!
n!+ +
...
+
(-1)n
+
...1!e-
x
=
1
-ex
-
e-
xxx3sin
x
=(2n
-1)!+
...
=1!
3!x2n-1+ +
...
+2§4.1
指数母函数例5§4.1
母函数的基本概念例
题4.1.2
指数母函数例5、设n是整数，求序列(p(n,0),p(n,1),…,p(n,n))的指数母函数fe(x)。(
)
(
)
(
)nxxnn
n
n0
1
n解：由定义4.2及公式P(n,r)=r!C(n,r),以及例1的结论，有fe
(
x)
=
p(n,
0)
+
p(n,1)
1!
+
...
+
p(n,
n)
n!=+
x
+
...
+
x=
(1
+
x)n§4.1
指数母函数例6§4.1
母函数的基本概念例
题4.1.2
指数母函数例6、求序列(p(0,0),
p(2,1),
p(4,2),…,p(2n,n),…)的指数母函数fe(x)。(
)
(
)
(
)
(
)nxx2
xn20
2
42nn0
1
2解：由定义4.2及公式P(n,r)=r!C(n,r)，以及例3的结论，有fe
(
x)
=
p(0,
0)
+
p(2,1)
1!
+
p(4,
2)
2!
+
...
+
p(2n,
n)
n!
+
...=+
x
+
x
+
...
+x
+
...=
(1
-
4
x)-1
2§4.1
指数母函数例7§4.1
母函数的基本概念例
题4.1.2
指数母函数例7、求序列{1,α,α2,…,αn,…}的指数母函数fe(x)。其中α是实数。解：由定义4.2，有特别地：若a
=1，则序列(1,1,…,1,…)的指数母函数为ex
。nxe2x1!x22!xnn!f
(
x)
=
1
+a+a+
...
+a+
...
=
ea§4.1
指数母函数例8例
题§4.1
母函数的基本概念4.1.2
指数母函数例8、求序列(1,
1×4,
1×4×7,…,1×4×7×…×(3n+1),…)的指数母函数。解：由定义4.2和二项式定理，有nnxxx
2
xnn
!3n
xnn
!n
!¥n
=0n
=1¥fe
(
x
)
=
1
+
(1
·
4)
1!
+
(1
·
4
·
7)
2
!
+
...
+
1
·
4
·
7
·
...
·
(3n
+
1)
n
!
+
...1
·
4
·
7
·
...
·
(3n
+
1)¥
(4
3
)·
(7
3
)·
...
·
(3n
+
1
3
)¥
(-
4
3
)·
(-
4
3
-
1)·
...
·
(-
4
3
-
n
+
1)(-3
x
)n
-
4n
=1
=
(1
-
3
x
)-
4
3=
=
1
+
n
=1=
1
+
=
1
+
n
3
(-3
x
)§4.1
母函数定理1定理4.1§4.1
母函数的基本概念4.1.2
指数母函数设f(x)、fe(x)分别为序列{an}的普通、指数母0e¥
-s函数，则
f
(
x)
=
e
f
(sx)ds将上式两边同乘以e-s并从0到¥积分得由分部积分法有故(sx)nn!¥n=0解：由指数母函数的定义4.2，有fe
(sx)
=
an000enne
axnn!¥¥¥
¥¥-s-se-s
sndsn=0e
f
(sx)ds
=ds
=
an=00¥sn
xnn!e-s
snds
=
n!0en¥-se
f
(sx)ds
=a
xn
=
f
(
x)¥n=0设A(x),B(x),C(x)分别是序列{an},{bn}和{cn}的普通母函数，则C(x)=A(x)+B(x)当且仅当ci=ai+bi,(i=0,1,…,r,…)§4.2
母函数运算定理2§4.2
母函数的基本运算定理4.2iC(x)=A(x)B(x)当且仅当ci
=ak
bi
-k
,(i=0,1,…,r,…)k
=0§4.2
母函数运算例1§4.2
母函数的基本运算例
题例1、设A(x)是序列{an}的普通母函数，则A(x)/(1-x)是序列{a0,a0+a1,…,a0+a1+…+an,…}的普通母函数。11-
x=
1
+
x
+
x2
+
...
+
xn
+
...故1(1
-x)是序列(1,1,...,1,...)的普通母函数。证明：由牛顿二项式定理知令B(x)=1(1
-x),根据上述定理有c0
=
a0
·1
=
a0c1
=
a0
·1
+
a1
·1
=
a0
+
a1......cn
=a0
·1
+a1
·1
+...+an
·1
=a0
+a1
+...+an故A(x)(1
-x)=A(x)·
B(x)是序列(a0
,a0
+a1
,...,
a0
+a1
+...+an
,...)的普通母函数。§4.2
母函数运算例2例
题例2、求和值。§4.2
母函数的基本运算ri
=0
i的2r¥i
=
0¥¥i
=
0i
=1=
i
2
x
i由牛顿二项式定理知(1-x
)-1
=
x
i
,将
上
式
两
端
对
x
微
分
再
乘
以
x
得
（x
1
-
x）-
2
=
ix
ii
=
0再
将
上
式
两
端
对
x
微
分
再
乘
以
x
得
x
(1
+
x（) 1
-
x）-
3故
x
(1
+
x（) 1
-
x）-
3是
序
列(
0
2
,
1
2
,
...,
r
2
,
...)的
普
通
母
函
数
。r故
c
=
解：先求序列(0
2
,1
2
,...,r
2
,...)的普通母函数。(
)
(
)(
)
(
)3!3!66iirx
2xi
2i
=
0i
=1i
2的
普
通
母
函
数
为
x
(1
+
x
)
·
1
=
x
+4
+
i
-
1ii
+
3i(
r
+
2
)(
r
+
1
)
r
(
r
+
1
)
r
(
r
-
1
)
r
(
r
+
1
)(
2
r
+
1
)r
+
2rr
+
1r+=+==
r
(
r
+
1
)(
2
r
+
1
)¥x
=
i
=
0（
1
-
x）3
1
-
x
（
1
-
x）4
（
1
-
x）4¥由推论1.10
.2
知(1-x
)-4
=故
x
(1
+
x
)
的
展
开
式
中
x
r的
系
数
为（
1
-
x）4r故
c
=
§4.2
母函数运算推论1§4.2
母函数的基本运算六个推论{0k推论4.2.1：若bak
-lk
‡
lk
<l，则B(x)=xl
A(x)=0
10
1
20
1
l
-1
l l
+1\
B(
x)
=
b
+
b
x
+
...
+
b
xl
-1
+
b
xl
+
bxl
+1
+
...=
0
+
0
+
...
+
0
+
a
xl
+
a
xl
+1
+
...=
xl
(a
+
a x
+
a
x2
+
...)=
xlA(
x)证明：
b0
=b1
=...=bl
-1
=0bl
=
a0
,
bl
+1
=
a1
,
...,
bk
=
ak
-l
,
...六个推论k推论4.2.1：若b=kxlka
x§4.2
母函数运算推论2§4.2
母函数的基本运算{0ak
-lk
‡
lk
<l，则B(x)=xl
A(x)l
-1k k
+lk
=0推论4.2.2：若b=a
，则B(x)=
A(x)-()20
1
212012lk
1
xl
1
xla
xl l
+1l
+2l
+1l
+2l
-1l
-1l
-1=
a
+
a x
+
a
x2
+
...l=a
x
+
axl
+1
+
axl
+2
+
...=A(
x)
-
a+
a
x+
a
x+
...
+
a
x1
k
=A(
x)
-xl
k
=0证明：B(
x)
=
b
+
b
x
+
b
x
+
...§4.2
母函数运算推论3§4.2
母函数的基本运算六个推论{0k推论4.2.1：若bak
-lk
‡
lk
<l，则B(x)=xl
A(x)=kxlkka
xl
-1k
+lk
=0推论4.2.2：若b=a
，则B(x)=
A(x)-k推论4.2.3：若bk
=
ai，则B(
x)
=
A(
x)
(1
-
x)i
=0见本节例1。§4.2
母函数运算推论4§4.2
母函数的基本运算六个推论¥
¥k
=0
j
=k推论4.2.4：若ak收敛，bk=
a
j，则B(x)=[A(1)-xA(x)](1
-x)20
1
22
2
0
11
:
b0
=
a0
+
a1
+
a2
+
...
=
A(1)x
:
b1
=
a1
+
a2
+
...
=
A(1)
-
a0x2
:
b
=
a
+
...
=
A(1)
-
a
-
a+)
...
...+...进行形式演算，有证明：对B(
x)
=
b
+
b
x
+
b
x01220
1
2B(
x)
=
A(1)(1
+
x
+
x2
+
...)
-
a
x(1
+
x
+
x2
+
...)-
a
x2
(1
+
x
+
x2
+
...)
-
...=
A(1)
-
x(a+
a x
+
a
x
+
...)
(1
+
x
+
x+
...)=
[A(1)
-
xA(
x)]
(1
-
x)0ak1
+
k
xk推论4.2.6：若b=
，则B(
x)
=
1
x
A(
x)dx§4.2
母函数运算推论5、6§4.2
母函数的基本运算六个推论¥
¥k
=0
j
=k推论4.2.4：若ak收敛，bk=
a
j，则B(x)=[A(1)-xA(x)](1
-x)推论4.2.5：若bk
=kak，则B(x)=xA¢(x)C(x)=A(x)B(x)当且仅当(i=0,1,…,r,…),§4.2
母函数定理3§4.2
母函数的基本运算设A(x),
B(x),
C(x)分别是序列{an}, {bn}和{cn}的指数母函数，则C(x)=A(x)+B(x)当且仅当ci=ai+bi,(i=0,1,…,r,…)定理4.3(ik
=0iikc
=a
bk i
-k§4.3
排列组合概述§4.3
在排列组合中的应用母函数有着极其广泛的应用，从本节开始介绍母函数在某些组合数学的问题中的应用。本节介绍普通母函数在组合中的应用和指数母函数在排列中的应用，主要是计数问题，也有部分方案方法问题。考虑三个不同的物体a、b、c的选取方法。(1
+
ax)(1
+
bx)(1
+
cx)=
1
+
(a
+
b
+
c)
x
+
(ab
+
bc
+
ca)
x2
+
(abc)
x3如果对选取方法的个数感兴趣，而不是对不同的选取方法感兴趣，则可令a=b=c=1，有(1
+
x)(1
+
x)(1
+
x)=
(1
+
x)3=
1
+
3
x
+
3
x2
+
x3§4.3
组合应用例1§4.3
在排列组合中的应用例
题4.3.1
在组合中的应用例1、有红球两只，白球、黄球各一只，试求有多少种不同的组合方案。随机组合解：设r,w,y分别代表红球，白球和黄球。(1
+
r
+
r
2
)(1
+
w)(1
+
y)
=
(1
+
r
+
r
2
)(1
+
y
+
w
+
yw)=
1
+
(r
+
y
+
w)
+
(r
2
+
ry
+
rw
+
yw)
+
(r
2
y
+
r
2
w
+
ryw)
+
r
2
yw由此可见，除一个球也不取的情况外，有：(a)取一个球的组合数为三，即分别取红，白，黄，三种；(b)取两个球的组合数为四，即两个红的，一红一黄，一红一白，一白一黄；(c)取三个球的组合数为三，即两红一黄，两红一白，一红一黄一白；(d)取四个球的组合数为一，即两红一黄一白。令取i个球的组合数为ai，则序列a0,a1,a2,a3,a4的普通母函数为f
(
x)
=
(1
+
x
+
x2
)(1
+
x)2
=
1
+
3
x
+
4
x2
+
3
x3
+
x4故共有1+3+4+3+1=12（或3×22=12）种组合方式。§4.3
组合应用例2例
题§4.3
在排列组合中的应用4.3.1
在组合中的应用例2、n个完全一样的球放到m个有标志的盒子中，不允许有空盒，问有多少种不同的方案？其中n≥m
重复组合((
)(
)
()(
)mnnnnnxm)xxnx¥n=0¥n¥n+mn=0n=m¥¥n=m解：由于不允许有空盒，令n个球放到m个有标志的盒子的方案数为an，序列{an}对应的普通母函数为f(x)。则f
(
x)
=
(
x
+
x2
+
...)(
x
+
x2
+
...)...(
x
+
x2
+
...)m
+
n
-1=
=
x(1
-
x)mm
+
n
-1n
-1=)x
=n
-
mn
-1n
-1=x
=m
-1m
-1n
-1m
-1(n=0故a
=§4.3
组合应用例3§4.3
在排列组合中的应用例
题4.3.1
在组合中的应用例3、某单位有8个男同志，5个女同志，现要组织一个由数目为偶数的男同志，和数目不少于2的女同志组成的小组，试求有多少种组成方式。随机组合解：令an为从8位男同志中抽取出n个的允许组合数。由于要男同志的数目必须是偶数，故序列{an}对应的普通母函数为f(x)=[(1+x)8+(1-x)8]/2类似女同志的允许组合数对应的普通母函数为g(x)=[(1+x)5-(1+5x)]令cn为符合要求的n个人组成的小组的数目，由乘法法则，序列{cn}对应的普通母函数为h(x)=f(x)×g(x)=[(1+x)8+(1-x)8]×[(1+x)5-(1+5x)]/2故总的组成方式数目为128×26=3328。§4.3
组合应用例4§4.3
在排列组合中的应用例
题4.3.1
在组合中的应用例4、证明从n个不同的物体中允许重复地选取r
个物体的方式数为F(n,r)=C(n+r-1,r)。证明：设ar表示从n个不同的物体中允许重复的选取r个物体的((
)1rrrxr
!)xr¥¥¥r
=0方式数。序列{ar}的普通母函数为
n=
(1
-
x)-nf
(
x)
=
(1
+
x
+
x2
+
...)n
=
1
-
x
-n(-n
-1)...(-n
-
r+1)(-x)r
!n(n
+1)...(n
+
r
-1)n
+
r
-1=n
+
r
-1r=
r
=0=
r
=0故ar
=F
(n,r
)=§4.3
组合应用例5§4.3
在排列组合中的应用例
题4.3.1
在组合中的应用例5、求从n个不同物体中允许重复地选取r个物体，但每个物体出现偶数次的方式数。(
)(
)
(
)
(
)((
)1122r2rn
2)xr¥r
=0解：设ar为所求的方式数。由于每个物体出现偶数次，故可用因子(1+x2+x4+…)示某一物体可以不选，或选取2次，或选取4次，…。因此序列{ar}的普通母函数为f
(
x)
=
(1
+
x2
+
x4
+
...)nn=
(1
-
x2
)-n=
1
-
x2
n
+1
4
n
+
2
63n
+
r
-1
2rr=
1
+x
+x
+x
+
...
+x
+
...n
+
r
-1=n
+
r
-1r故a
=§4.3
组合应用例6§4.3
在排列组合中的应用4.3.1
在组合中的应用例6、在一个书架上共有16本书，其中4例
题
本是高等数学，3本是普通物理，4本是数据结构，5本是离散数学。求从中选取r本数的方式数，其中r=12。解：这实际上是求重集{4*M,3*P,4*S,5*D}的12−组合数。设ar是选取r本书的方式数。由于高等数学最多只能选取4本，普通物理最多只能选取3本，数据结构最多只能选取4本，离散数学最多只能选取5本，故序列{ar}的普通母函数为f
(
x)
=
(1
+
x
+
x2
+
x3
+
x4
)(1
+
x
+
x2
+
x3
)(1
+
x
+
x2
+
x3
+
x4
)(1
+
x
+
x2
+
x3
+
x4
+
x5
)=
1
+
4x
+10x2
+
20x3
+
34x4
+
50x5
+
65x6
+
76x7
+
80x8+76x9
+
65x10
+
50x11
+
34x12
+
20x13
+10x14
+
4x15
+
x16取f(x)展开式中xr的系数即为所求的方式数。当r=12时，x12的系数为34，即a12=34。§4.3
组合应用例7§4.3
在排列组合中的应用4.3.1
在组合中的应用例
题例7、现有2n个A，2n个B，2n个C，求从它们之中选出3n个字母的不同的方式数。解：这个问题实际上是求重集{2n*A,2n*B,2n*C}的3n−组合数。(
)()
(
)2设ar为所求的方2式数。则2n序3
列{ar}的普通母函数为k3nk
!x¥k
=0¥2n+14n+26n+3¥2n+14n+26n+3k
=0f
(
x)
=
(1
+
x
+
x
+
...
+
x
)
1
-
x2n+1
3(-3)(-4)...(-3
-
k
+1)3
=
(-x)k
1
-
xk
!3
·4
·...·(k
+
2)
k
x
k
+
2=
(1
-
3
x
+
3
x
-
x=
(1
-
3
x+
3
x
-
x3n
+
2n
+12-
3=
(1
-
x2n+1
)
1
+)1
+
k
=0)显然，上式中x的系数为(
)
(
)3n3n
+
22n
+122-
3故r
=
3n时，有a
=§4.3
排列应用例8例
题§4例.38、在由排1,列2,3组,4四合个中数的字应组用成的五位数中，要求数1出现次数不超过2次，但不能不4.3.2
在排列中的出现应；用2出现不超过1次；3出现次数可达3次，也可不出现；4出现次数为偶数。求满足上述条件的数的个数。容斥原理由此可见满足条件的5位数ar=215个。x
xx
2
x
2
x
3
x
2
x
4x
6
x
723453127)2
23
241848
1442
3
2448x101
128848
288解：设满足条件的r位数的个数为ar，序列{ar}的指数母函数为fe
(
x
)
=
(1!
+
2!
)(1
+
x
)(1
+
1!
+
2!
+
3!
)(1
+
2!
+
4!
)=
(
x
+
x
+x
3
)(1
+
x
+
x
2
+
x
+x
+x
+
+=
x
+
5
x
2
+
3
x
3
+
8
x
4
+
43
x
5
+
43
x
6+
17
x
7
+x
8
+
1
x
9
+xx
2x
3x
4x
5x
6x
7x
8x
9x101!
2!3!4!5!6!7
!
8!
9!10
!=48+
5
+
18
+
64
+
215
+
645+
1785
+
140+
7650
+
12600§4.3
排列应用例9§4.3
在排列组合中的应用例
题4.3.2
在排列中的例9应、用求1,3,5,7,9五个数字组成的n位数的个数，要求其中3,7出现的次数为偶数，其他1,5,9出现的次数不加限制。解：设满足上述条件的r位数的个数为ar，序列{ar}的指数母函数为xxxenxnx2
x4
x2
x32
3x2
x3x2
x42 3
x2
x5
x3
x2!
4!2!
3!2!
3!12!
4!21114415n43n
xn4n!n!x
-
x-2
x
3
x¥¥n=0
n=0fe
(
x)
=
(1
+
+ +
...)
(1
+
x
++ +
...)- +
...\
1
+
+ +
...
=
(e+
e-
)\
f
(
x)
=
(e+
e
)
e=
(e
+
2
+
e)e
=
(e+
2e
+
e
)=
(+n=0e-
x
=
1
-
x
+nnnxn1n!
4n!4¥¥)
=(5
+
2·3
+1)\
a
=
1
(5n
+
2·3n
+1)x
+
2n=0§4.3
排列应用例10§4.3
在排列组合中的应用nr4.3.2
在排列中的应用例10、证明从n个不同的物体中允许重复例
题
地选取r个物体的排列数为nr。证明：这个问题实际上是证明重集B={∞*b1,∞*b2,…,∞*bn}的r−排列数为nr。设ar为所求的排列数。则序列{ar}的指数母函数为x2
xrxrr
!¥fe
(
x)
=
(1
+
x
+
2!
+
...
+
r
!
+
...)a
=
nr=
(ex
)n
=
enx
=
nrr
=0故有§4.3
排列应用例11例
题§4.3例在11排、用列红组、合白中、的绿应三用种颜色给1×n棋盘中的正方形着色，要求偶数个正方形着红4.3.2
在排列中的色应，用而着白色和绿色的正方形个数不加限制，求不同的着色方式数。证明：若用R,W和G分别表示红、白和绿三种颜色，则该问题实际上是求重集B={∞*R,∞*W,∞*G}的n−排列数，其中要求R出现偶数次。设an为所求的排列数。则序列{an}的指数母函数为(
)nnnxnx2
x4
x222!
4!
2!3n!n!212n!2¥¥n=0xn¥n=0fe
(
x)
=
(1
+
+ +
...)(1
+
x
+ +
...)=
1
(ex
+
e-
x
)e2
x
=
1
(e3
x
+
ex
)21
2xn
=+
n=0=3
+1故有a
=
1
(3n
+1)§4.3
排列应用例12§4.3
在排列组合中的应用4.3.2
在排列中的应用例12、在所有的n位数中，包含数字3,8,9，例
题
但不包含数字0,4的数有多少？解：这个问题实际上是求重集
B={∞*1,∞*2,∞*3,∞*5,∞*6,∞*7,∞*8,∞*9}的n−排列数，其中要求3,8,9至少出现一次，而其他的数不加限制。设符合题意的数(
)en
n
n
nnxxn5有an个。则序列{an2}的指数母函3
数为x3
x22!
3!
2!n!¥n=0
f
(
x)
=
x
++ +
...1
+
x
+ +
...
=
(ex
-1)3
e5
x
=
(e3
x
-
3e2
x
+
3ex
-1)e5
x=
e8
x
-
3e7
x
+
3e6
x
-e5
x=8
-
3·7
+
3·6
-5a
=
8n
-
3·7n
+
3·6n
-5n故有§4.3
排列应用例13§4.3
在排列组合中的应用例
题4.3.2
在排列中的应用例13、求1,2,3,4,5五个数字组成的r位数的个数，要求其中1出现的次数与2出现的次数的和必须是偶数。解：设an为符合题意的个数。由于1出现的次数与2出现的次数的和为偶数，可分为两种情况：①1出现的次数与2出现的次数都为偶数；②1出现的次数与2出现的次数都为奇数。由加法法则知，序列{an}的指数母函数为(
)nnxnx2
x4x2x3
x5x22!
4!2!3!
5!2!2222n!2¥n=02
3fe
(
x)
=
1
++ +
...
1
+
x
++
...
2
3+
x
++ +
...
1
+
x
++
...
ex
+
e-
x
2
ex
-e-
x
2e5
x
+
ex=
e3
x
+
e3
x
=1
=5
+1故有
a
=
1
(5n
+1)这是母函数的应用实例之一。整数的拆分就是把整数分成若干个正整数部分，并且不考虑各部分的次序，不同的拆分方法的总数叫拆分数P(n)。相当于把n个无区别的球放到
1≤m≤n个无标志的盒子中的方法数。§4.4
整数的拆分概念§4.4
整数的拆分1(1
-
x
)(1
-
x2
)(1
-
x3
)=
(1
+
x
+
x2
+
...)(1
+
x2
+
x4
+
...)(1
+
x3
+
x6
+
...)=
1
+
x
+
2
x2
+
3
x3
+
4
x4
+
5
x5
+
7
x6
+
...如：§4.4
整数的拆分定理4§4.4
整数的拆分定理4.4设a,b,c...为大于0
的整数，则1/[(1-xa)(1-xb)(1-xc)…]的级数展开式中xn的系数等于把正整数n拆分为a,b,c…的和的方法数P(n)。证明：注意到1(1
-
xa
)(1
-
xb
)(1
-
xc
)=
(1
+
xa
+
x2a
+
...)(1
+
xb
+
x2b
+
...)(1
+
xc
+
x2c
+
...)如果项xn是由x3a,xb,x2c,…的乘积所组成的，则n
=
a
+
a
+
a
+
b
+
c
+
c
+
...于是，每当n可以拆分为a,b,c的和时，xn就会出现，这就证明了定理的结论。§4.4
整数的拆分例1例
题§4.4
整数的拆分例1、若有1克、2克、3克、4克的砝码各一枚，问能称出哪几种重量？有几种可能方案？证明：我们采用如下办法来产生拆分数的普通母函数：(1
+
x)(1
+
x2
)(1
+
x3
)(1
+
x4
)
=
(1
+
x
+
x2
+
x3
)(1
+
x3
+
x4
+
x7
)=
1
+
x
+
x2
+
2
x3
+
2
x4
+
2
x5
+
2
x6
+
2
x7
+
x8
+
x9
+
x10从右端的母函数知能称出从1克到10克的重量，系数便是方案数。例如右端有2x5
项，即称出5克的方案有2种，5=2+3=1+4。同样6=1+2+3=2+4，10=1+2+3+4，即称出6克的方案有2种，称出10克的方案有1种。§4.4
整数的拆分例2§4.4
整数的拆分例2、求用1分、2分、3分的邮票贴出不同数值的方案数。1
11
1解：因邮票允许重复，故普通母函数为f
(
x)
=
(1
+
x
+
x2
+
...)(1
+
x2
+
x4
+
...)(1
+
x3
+
x6
+
...)=·
·
=1
-
x
1
-
x2
1
-
x3
1
-
x
-
x2
+
x4
+
x5
-
x61分
2分3分=
1
+
x
+
2
x2
+
3
x3
+
4
x4
+
5
x5
+
7
x6
+
...以其中x4为例，其系数为4，即4拆分成1、2、3之和的拆分数为4，即
4
=
1
+1
+1
+1
=
1
+1
+
2
=
1
+
3
=
2
+
2例
题§4.4
整数的拆分例3§4.4
整数的拆分例3、若有1克的砝码3枚，2克的4枚，4克的2枚，问能称出哪些重量？各有几种方案？解：
f
(
x)
=
(1
+
x
+
x2
+
x3
)(1
+
x2
+
x4
+
x6
+
x8
)(1
+
x4
+
x8
)4克2枚1克3枚
2克4枚=
(1
+
x
+
2
x2
+
2
x3
+
2
x4
+
2
x5
+
2
x6+
2
x7
+
2
x8
+
2
x9
+
x10
+
x11
)(1
+
x4
+
x8
)=
1
+
x
+
2
x2
+
2
x3
+
3
x4
+
3
x5
+
4
x6
+
4
x7+
5
x8
+
5
x9
+
5
x10
+
5
x11
+
4
x12
+
4
x13+
3
x14
+
3
x15
+
2
x16
+
2
x17
+
x18
+
x19上面的1+x4+x8项表示4克砝码只有两枚，或不取，或取一枚，或取2枚。x8项的系数为5，说明称8克的方案有5种：8
=
1
+1
+
2
+
2
+
2=2
+
2
+
4=1
+1
+
2
+
4=2
+
2
+
2
+
2=4
+
4例
题§4.4
整数的拆分例4§4.4
整数的拆分例4、整数n拆分成1,2,3,…,m的和，并允许重复，求其母函数。如若其中m至少出现一次，其母函数如何？解：若整数n拆分成1,2,3,…,m的和，并允许重复，其普通母函数为：若拆分中m至少出现一次，其普通母函数为：上式的组合意义：整数n拆分成1到m的和的拆分数减去拆分成1到m-1的和的拆分数，即为至少出现一个m的拆分数。11
1
1
1f
(
x)
=
(1
+
x
+
x2
+
...)(1
+
x2
+
x4
+
...)...(1
+
xm
+
x2m
+
...)=·
·...·
=1
-
x
1
-
x2
1
-
xm
(1
-
x)(1
-
x2
)...(1
-
xm
)xm21
1f
(
x)
=
(1
+
x
+
x2
+
...)(1
+
x2
+
x4
+
...)...(
xm
+
x2m
+
...)1
-
(1
-
xm
)=
=(1
-
x)(1
-
x2
)...(1
-
xm
)
(1
-
x)(1
-
x2
)...(1
-
xm
-1
)(1
-
xm
)=-(1
-
x)(1
-
x2
)...(1
-
xm
)
(1
-
x)(1
-
x2
)...(1
-
xm
-1
)例
题§4.4
整数的拆分定义§4.4
整数的拆分定义4.3用Pk(n)表示n拆分为1,2,…,k允许重复的方法数。用Po(n)表示n拆分为奇整数的方法数。用Pd(n)表示n拆分为不同整数的方法数。用Pt(n)表示n拆分为2的不同幂（1,2,4,…）的方法数。数的拆分推论§4.4
整§4.4
整数的拆分四个推论推论4.4.1：{P3(n)}的普通母函数是1/[(1-x)(1-x2)(1-x3)]推论4.4.2：{P
(n)}的普通母函数是1/[(1-x)(1-x2)…(1-xk)]k推论4.4.3：{P(n)}的普通母函数是1/[(1-x)(1-x2)(1-x3)…]推论4.4.4：{Po(n)}的普通母函数是1/[(1-x)(1-x3)(1-x5)…]§4.4
整数的拆分定理5§4.4
整数的拆分定理4.5设a,b,c…为不同的正整数，则(1+xa)(1+xb)(1+xc)…的级数展开式中xn
的系数就是把n
拆分为a,b,c…的和，且a,b,c…最多只出现一次的方法数。推论4.5.1：{Pd(n)}的普通母函数为(1+x)(1+x2
)(1+x3)(1+x4)…推论4.5.2：{Pt(n)}的普通母函数是(1+x)(1+x2)(1+x4)(1+x8)…两个推论§4.4
整数的拆分定理6-1§4.4
整数的拆分定理4.6Euler定理：Po(n)=Pd(n)等式右端正好是Po(n)的普通母函数（推论4.4.4)
。所以Po(n)=Pd(n)，即把n拆分成奇整数的和的方法数等于把n拆分成不同的整数和的方法数。2
341证明：根据推论4.5.1，Pd(n)的普通母函数为f
(
x)
=
(1
+
x)(1
+
x2
)(1
+
x3
)(1
+
x4
)...1
-
x2
1
-
x4
1
-
x61
-
x8=
,
...1
-
x41
-
x2
1
-
x4
1
-
x6
1
-
x8\
f
(
x)
=
·1
-
x
1
-
x2·
·
·...1
-
x3
1
-
x4=(1
-
x
)(1
-
x3
)(1
-
x5
)(1
-
x7
)...1
+
x
=
,
1
+
x
=
,
1
+
x
=
,
1
+
x1
-
x
1
-
x2
1
-
x3§4.4
整数的拆分定理6-2§4.4
整数的拆分定理4.6Euler定理：Po(n)=Pd(n)可以验证当n=7的情况：7
=
77
=
5
+1
+17
=
3
+
3
+17
=
3
+1
+1
+1
+17
=
1
+1
+1
+1
+1
+1
+1\
Po
(7)
=
5于是
Po
(7)
=
Pd
(7)7
=
77
=
6
+17
=
5
+
27
=
4
+
37
=
4
+
2
+1Pd
(7)
=
5§4.4
整数的拆分定理7§4.4
整数的拆分定理4.7Sylvester定理：对任意正整数n有Pt(n)=1证明I：因为任何一个正整数都可惟一地用一二进制数来表示，而一个二进制数又可惟一地表示成2的次幂的和，由此即得结论。上式的左端正好是Pt(n)的普通母函数（推论4.5.2),2
48,...1nnt¥
¥n=0证明II：因为序列{1,1,1,…}的普通母函数为f
(
x)
=
1
+
x
+
x2
+
x3
+
...1
-
x2
1
-
x4
1
-
x81
-
x161
+
x
=
,
1
+
x
=
,
1
+
x
=
,
1
+
x
=1
-
x
1
-
x2
1
-
x4
1
-
x8\
(1
+
x
)(1+
x2
)(1
+
x4
)(1
+
x8
)...1
-
x2
1
-
x4
1
-
x8
1
-
x16=
·
·
·1
-
x
1
-
x2
1
-
x4
1
-
x8...
=
=
f
(
x)1
-
x\P
(n)
x
=1·x\
Pt
(n)
=
1n=0§4.4
整数的拆分例5§4.4
整数的拆分例
题例5、设有1,2,4,8,16,32克砝码各一枚，试问能称出哪些重量？分别有几种方案？从普通母函数f(x)可以得知，用这些砝码可以称出从0克到63克的重量，而且办法都是惟一的。实际是0到63的数的二进制表示是惟一的。632
63
kk
=0证明：
f
(
x
)
=
(1
+
x)(1
+
x2
)(1
+
x4
)(1
+
x8
)(1
+
x16
)(1
+
x32
)1
-
x2
1
-
x4
1
-
x8
1
-
x16
1
-
x32
1
-
x64=
·
·
·
·
·1
-
x
1
-
x2
1
-
x4
1
-
x8
1
-
x1
温馨提示
- 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2026住院医师规范化培训考试（急诊科）历年参考题库含答案详解
- 2026年呼和浩特市新城区事业单位人员招聘笔试备考试题及答案详解
- 2025年桂林市秀峰区事业单位人员招聘笔试试题及答案详解
- 2026年育婴员基础知识职业技能试卷及答案
- 2026年眼科护理分层培训专项试卷及答案
- Labubu奇幻世界模版
- 会计专业技术资格中级《中级会计实务》考前速记清单
- 2026年公共营养师理论模拟试卷附答案
- 2026秋苏少版小学音乐三年级上册(新教材)教学计划
- 2026国考牡丹江市市场监管岗位行测题库及答案
- fde+行业研究报告-霞光智库-202609
- 液化气站安全试题及答案
- 江苏省常州市2026年中考数学试卷（含答案）
- 各快递公司应急预案(3篇)
- 2026年国庆节祖国发展成就课件
- 2026-2030中国应急救援装备行业发展分析及发展趋势研究报告
- 2026江苏省高一英语月考综合卷(阶段检测)
- 2025云南红河投资有限公司第二批次招聘3人笔试历年常考点试题专练附带答案详解2套试卷
- （2026年）气管插管术的配合与护理课件
- 2026年中原农业保险股份有限公司招聘67人备考题库附答案详解
- 《钢结构设计原理》课件 第5章 受弯构件
评论
0/150
提交评论