第4章母函數(shù)回顧前一章——容斥原理：本章重點介紹母函數(shù)（普通母函數(shù)、指數(shù)母函數(shù)）的基本概念及其在排列組合中的應(yīng)用：母函數(shù)的基本概念母函數(shù)的基本運算母函數(shù)在排列、組合中的應(yīng)用整數(shù)拆分母函數(shù)在組合恒等式中的應(yīng)用基本原理重集的r-組合錯排、有限制排列§4.1普通母函數(shù)概念§4.1

母函數(shù)的基本概念定義4.14.1.1

普通母函數(shù)給定一無窮序列(a0,a1,…an,…)(簡記為{an})，稱函數(shù)

f

(

x)

=為序列{an}的普通母函數(shù)（發(fā)生、iia

x￥生成函數(shù)）i

=0。注：f(x)是無窮級數(shù)，不管其收斂性；

x為形式變元，f(x)為形式冪級數(shù)；序列與母函數(shù)一一對應(yīng)；母函數(shù)是序列的另一表達(dá)形式；有限序列也可用母函數(shù)表示；可與二項式定理結(jié)合應(yīng)用?！?.1

普通母函數(shù)例1§4.1

母函數(shù)的基本概念例

題4.1.1

普通母函數(shù)例

1

、

求

序

列

(C(n,0),C(n,1),C(n,2),…,C(n,n))的普通母函數(shù)。解：由定義4.1及二項式定理的推論1.9.2有0

1

nf

(

x)

=

n

+

n

x

+

...

+

n

xn=

(1

+

x)n§4.1

普通母函數(shù)例2例

題§4.1

母函數(shù)的基本概念4.1.1

普通母函數(shù)例2、求序列(C(n-1,0),-C(n,1),

C(n+1,2),…,(-1)kC(n+k-1,k),…)的普通母函數(shù)。解：由定義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

普通母函數(shù)例3例

題§4.1

母函數(shù)的基本概念例3

、證明(1-4x)-1/2

是序列(C(0,0),

C(2,1),4.1.1

普通母函數(shù)C(4,2),…,C(2n,n),…)的普通母函數(shù)。(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),…)的普通母函數(shù)。(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

普通母函數(shù)例4§4.1

母函數(shù)的基本概念例

題4.1.1

普通母函數(shù)例4、求序列(0,

1×2×3,

2×3×4,…,n(n+1)(n+2),…)的普通母函數(shù)。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),...)的普通母函數(shù)。§4.1

指數(shù)母函數(shù)概念§4.1

母函數(shù)的基本概念定義4.24.1.2

指數(shù)母函數(shù)給定一無窮序列(a0,a1,…an,…)（簡記為{an}），稱注：fe(x)也是形式冪函數(shù)。經(jīng)?？山Y(jié)合以下公式運算：為序列{an}的指數(shù)母函數(shù)。xii

!￥i

=0函數(shù)

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

指數(shù)母函數(shù)例5§4.1

母函數(shù)的基本概念例

題4.1.2

指數(shù)母函數(shù)例5、設(shè)n是整數(shù)，求序列(p(n,0),p(n,1),…,p(n,n))的指數(shù)母函數(shù)fe(x)。(

)

(

)

(

)nxxnn

n

n0

1

n解：由定義4.2及公式P(n,r)=r!C(n,r),以及例1的結(jié)論，有fe

(

x)

=

p(n,

0)

+

p(n,1)

1!

+

...

+

p(n,

n)

n!=+

x

+

...

+

x=

(1

+

x)n§4.1

指數(shù)母函數(shù)例6§4.1

母函數(shù)的基本概念例

題4.1.2

指數(shù)母函數(shù)例6、求序列(p(0,0),

p(2,1),

p(4,2),…,p(2n,n),…)的指數(shù)母函數(shù)fe(x)。(

)

(

)

(

)

(

)nxx2

xn20

2

42nn0

1

2解：由定義4.2及公式P(n,r)=r!C(n,r)，以及例3的結(jié)論，有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

指數(shù)母函數(shù)例7§4.1

母函數(shù)的基本概念例

題4.1.2

指數(shù)母函數(shù)例7、求序列{1,α,α2,…,αn,…}的指數(shù)母函數(shù)fe(x)。其中α是實數(shù)。解：由定義4.2，有特別地：若a

=1，則序列(1,1,…,1,…)的指數(shù)母函數(shù)為ex

。nxe2x1!x22!xnn!f

(

x)

=

1

+a+a+

...

+a+

...

=

ea§4.1

指數(shù)母函數(shù)例8例

題§4.1

母函數(shù)的基本概念4.1.2

指數(shù)母函數(shù)例8、求序列(1,

1×4,

1×4×7,…,1×4×7×…×(3n+1),…)的指數(shù)母函數(shù)。解：由定義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

母函數(shù)定理1定理4.1§4.1

母函數(shù)的基本概念4.1.2

指數(shù)母函數(shù)設(shè)f(x)、fe(x)分別為序列{an}的普通、指數(shù)母0e￥

-s函數(shù)，則

f

(

x)

=

e

f

(sx)ds將上式兩邊同乘以e-s并從0到￥積分得由分部積分法有故(sx)nn!￥n=0解：由指數(shù)母函數(shù)的定義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設(shè)A(x),B(x),C(x)分別是序列{an},{bn}和{cn}的普通母函數(shù)，則C(x)=A(x)+B(x)當(dāng)且僅當(dāng)ci=ai+bi,(i=0,1,…,r,…)§4.2

母函數(shù)運算定理2§4.2

母函數(shù)的基本運算定理4.2iC(x)=A(x)B(x)當(dāng)且僅當(dāng)ci

=ak

bi

-k

,(i=0,1,…,r,…)k

=0§4.2

母函數(shù)運算例1§4.2

母函數(shù)的基本運算例

題例1、設(shè)A(x)是序列{an}的普通母函數(shù)，則A(x)/(1-x)是序列{a0,a0+a1,…,a0+a1+…+an,…}的普通母函數(shù)。11-

x=

1

+

x

+

x2

+

...

+

xn

+

...故1(1

-x)是序列(1,1,...,1,...)的普通母函數(shù)。證明：由牛頓二項式定理知令B(x)=1(1

-x),根據(jù)上述定理有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

,...)的普通母函數(shù)?！?.2

母函數(shù)運算例2例

題例2、求和值。§4.2

母函數(shù)的基本運算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

,

...)的

普

通

母

函

數(shù)

。r故

c

=

解：先求序列(0

2

,1

2

,...,r

2

,...)的普通母函數(shù)。(

)

(

)(

)

(

)3!3!66iirx

2xi

2i

=

0i

=1i

2的

普

通

母

函

數(shù)

為

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的

系

數(shù)

為（

1

-

x）4r故

c

=

§4.2

母函數(shù)運算推論1§4.2

母函數(shù)的基本運算六個推論{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

母函數(shù)運算推論2§4.2

母函數(shù)的基本運算{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

母函數(shù)運算推論3§4.2

母函數(shù)的基本運算六個推論{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見本節(jié)例1?！?.2

母函數(shù)運算推論4§4.2

母函數(shù)的基本運算六個推論￥

￥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+)

...

...+...進(jìn)行形式演算，有證明：對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

母函數(shù)運算推論5、6§4.2

母函數(shù)的基本運算六個推論￥

￥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)當(dāng)且僅當(dāng)(i=0,1,…,r,…),§4.2

母函數(shù)定理3§4.2

母函數(shù)的基本運算設(shè)A(x),

B(x),

C(x)分別是序列{an}, {bn}和{cn}的指數(shù)母函數(shù)，則C(x)=A(x)+B(x)當(dāng)且僅當(dāng)ci=ai+bi,(i=0,1,…,r,…)定理4.3(ik

=0iikc

=a

bk i

-k§4.3

排列組合概述§4.3

在排列組合中的應(yīng)用母函數(shù)有著極其廣泛的應(yīng)用，從本節(jié)開始介紹母函數(shù)在某些組合數(shù)學(xué)的問題中的應(yīng)用。本節(jié)介紹普通母函數(shù)在組合中的應(yīng)用和指數(shù)母函數(shù)在排列中的應(yīng)用，主要是計數(shù)問題，也有部分方案方法問題?？紤]三個不同的物體a、b、c的選取方法。(1

+

ax)(1

+

bx)(1

+

cx)=

1

+

(a

+

b

+

c)

x

+

(ab

+

bc

+

ca)

x2

+

(abc)

x3如果對選取方法的個數(shù)感興趣，而不是對不同的選取方法感興趣，則可令a=b=c=1，有(1

+

x)(1

+

x)(1

+

x)=

(1

+

x)3=

1

+

3

x

+

3

x2

+

x3§4.3

組合應(yīng)用例1§4.3

在排列組合中的應(yīng)用例

題4.3.1

在組合中的應(yīng)用例1、有紅球兩只，白球、黃球各一只，試求有多少種不同的組合方案。隨機(jī)組合解：設(shè)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)取一個球的組合數(shù)為三，即分別取紅，白，黃，三種；(b)取兩個球的組合數(shù)為四，即兩個紅的，一紅一黃，一紅一白，一白一黃；(c)取三個球的組合數(shù)為三，即兩紅一黃，兩紅一白，一紅一黃一白；(d)取四個球的組合數(shù)為一，即兩紅一黃一白。令取i個球的組合數(shù)為ai，則序列a0,a1,a2,a3,a4的普通母函數(shù)為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）種組合方式?！?.3

組合應(yīng)用例2例

題§4.3

在排列組合中的應(yīng)用4.3.1

在組合中的應(yīng)用例2、n個完全一樣的球放到m個有標(biāo)志的盒子中，不允許有空盒，問有多少種不同的方案？其中n≥m

重復(fù)組合((

)(

)

()(

)mnnnnnxm)xxnx￥n=0￥n￥n+mn=0n=m￥￥n=m解：由于不允許有空盒，令n個球放到m個有標(biāo)志的盒子的方案數(shù)為an，序列{an}對應(yīng)的普通母函數(shù)為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

組合應(yīng)用例3§4.3

在排列組合中的應(yīng)用例

題4.3.1

在組合中的應(yīng)用例3、某單位有8個男同志，5個女同志，現(xiàn)要組織一個由數(shù)目為偶數(shù)的男同志，和數(shù)目不少于2的女同志組成的小組，試求有多少種組成方式。隨機(jī)組合解：令an為從8位男同志中抽取出n個的允許組合數(shù)。由于要男同志的數(shù)目必須是偶數(shù)，故序列{an}對應(yīng)的普通母函數(shù)為f(x)=[(1+x)8+(1-x)8]/2類似女同志的允許組合數(shù)對應(yīng)的普通母函數(shù)為g(x)=[(1+x)5-(1+5x)]令cn為符合要求的n個人組成的小組的數(shù)目，由乘法法則，序列{cn}對應(yīng)的普通母函數(shù)為h(x)=f(x)×g(x)=[(1+x)8+(1-x)8]×[(1+x)5-(1+5x)]/2故總的組成方式數(shù)目為128×26=3328?！?.3

組合應(yīng)用例4§4.3

在排列組合中的應(yīng)用例

題4.3.1

在組合中的應(yīng)用例4、證明從n個不同的物體中允許重復(fù)地選取r

個物體的方式數(shù)為F(n,r)=C(n+r-1,r)。證明：設(shè)ar表示從n個不同的物體中允許重復(fù)的選取r個物體的((

)1rrrxr

!)xr￥￥￥r

=0方式數(shù)。序列{ar}的普通母函數(shù)為

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

組合應(yīng)用例5§4.3

在排列組合中的應(yīng)用例

題4.3.1

在組合中的應(yīng)用例5、求從n個不同物體中允許重復(fù)地選取r個物體，但每個物體出現(xiàn)偶數(shù)次的方式數(shù)。(

)(

)

(

)

(

)((

)1122r2rn

2)xr￥r

=0解：設(shè)ar為所求的方式數(shù)。由于每個物體出現(xiàn)偶數(shù)次，故可用因子(1+x2+x4+…)示某一物體可以不選，或選取2次，或選取4次，…。因此序列{ar}的普通母函數(shù)為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

組合應(yīng)用例6§4.3

在排列組合中的應(yīng)用4.3.1

在組合中的應(yīng)用例6、在一個書架上共有16本書，其中4例

題

本是高等數(shù)學(xué)，3本是普通物理，4本是數(shù)據(jù)結(jié)構(gòu)，5本是離散數(shù)學(xué)。求從中選取r本數(shù)的方式數(shù)，其中r=12。解：這實際上是求重集{4*M,3*P,4*S,5*D}的12?組合數(shù)。設(shè)ar是選取r本書的方式數(shù)。由于高等數(shù)學(xué)最多只能選取4本，普通物理最多只能選取3本，數(shù)據(jù)結(jié)構(gòu)最多只能選取4本，離散數(shù)學(xué)最多只能選取5本，故序列{ar}的普通母函數(shù)為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的系數(shù)即為所求的方式數(shù)。當(dāng)r=12時，x12的系數(shù)為34，即a12=34?！?.3

組合應(yīng)用例7§4.3

在排列組合中的應(yīng)用4.3.1

在組合中的應(yīng)用例

題例7、現(xiàn)有2n個A，2n個B，2n個C，求從它們之中選出3n個字母的不同的方式數(shù)。解：這個問題實際上是求重集{2n*A,2n*B,2n*C}的3n?組合數(shù)。(

)()

(

)2設(shè)ar為所求的方2式數(shù)。則2n序3

列{ar}的普通母函數(shù)為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的系數(shù)為(

)

(

)3n3n

+

22n

+122-

3故r

=

3n時，有a

=§4.3

排列應(yīng)用例8例

題§4例.38、在由排1,列2,3組,4四合個中數(shù)的字應(yīng)組用成的五位數(shù)中，要求數(shù)1出現(xiàn)次數(shù)不超過2次，但不能不4.3.2

在排列中的出現(xiàn)應(yīng)；用2出現(xiàn)不超過1次；3出現(xiàn)次數(shù)可達(dá)3次，也可不出現(xiàn)；4出現(xiàn)次數(shù)為偶數(shù)。求滿足上述條件的數(shù)的個數(shù)。容斥原理由此可見滿足條件的5位數(shù)ar=215個。x

xx

2

x

2

x

3

x

2

x

4x

6

x

723453127)2

23

241848

1442

3

2448x101

128848

288解：設(shè)滿足條件的r位數(shù)的個數(shù)為ar，序列{ar}的指數(shù)母函數(shù)為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

排列應(yīng)用例9§4.3

在排列組合中的應(yīng)用例

題4.3.2

在排列中的例9應(yīng)、用求1,3,5,7,9五個數(shù)字組成的n位數(shù)的個數(shù)，要求其中3,7出現(xiàn)的次數(shù)為偶數(shù)，其他1,5,9出現(xiàn)的次數(shù)不加限制。解：設(shè)滿足上述條件的r位數(shù)的個數(shù)為ar，序列{ar}的指數(shù)母函數(shù)為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

排列應(yīng)用例10§4.3

在排列組合中的應(yīng)用nr4.3.2

在排列中的應(yīng)用例10、證明從n個不同的物體中允許重復(fù)例

題

地選取r個物體的排列數(shù)為nr。證明：這個問題實際上是證明重集B={∞*b1,∞*b2,…,∞*bn}的r?排列數(shù)為nr。設(shè)ar為所求的排列數(shù)。則序列{ar}的指數(shù)母函數(shù)為x2

xrxrr

!￥fe

(

x)

=

(1

+

x

+

2!

+

...

+

r

!

+

...)a

=

nr=

(ex

)n

=

enx

=

nrr

=0故有§4.3

排列應(yīng)用例11例

題§4.3例在11排、用列紅組、合白中、的綠應(yīng)三用種顏色給1×n棋盤中的正方形著色，要求偶數(shù)個正方形著紅4.3.2

在排列中的色應(yīng)，用而著白色和綠色的正方形個數(shù)不加限制，求不同的著色方式數(shù)。證明：若用R,W和G分別表示紅、白和綠三種顏色，則該問題實際上是求重集B={∞*R,∞*W,∞*G}的n?排列數(shù)，其中要求R出現(xiàn)偶數(shù)次。設(shè)an為所求的排列數(shù)。則序列{an}的指數(shù)母函數(shù)為(

)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

排列應(yīng)用例12§4.3

在排列組合中的應(yīng)用4.3.2

在排列中的應(yīng)用例12、在所有的n位數(shù)中，包含數(shù)字3,8,9，例

題

但不包含數(shù)字0,4的數(shù)有多少？解：這個問題實際上是求重集

B={∞*1,∞*2,∞*3,∞*5,∞*6,∞*7,∞*8,∞*9}的n?排列數(shù)，其中要求3,8,9至少出現(xiàn)一次，而其他的數(shù)不加限制。設(shè)符合題意的數(shù)(

)en

n

n

nnxxn5有an個。則序列{an2}的指數(shù)母函3

數(shù)為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

排列應(yīng)用例13§4.3

在排列組合中的應(yīng)用例

題4.3.2

在排列中的應(yīng)用例13、求1,2,3,4,5五個數(shù)字組成的r位數(shù)的個數(shù)，要求其中1出現(xiàn)的次數(shù)與2出現(xiàn)的次數(shù)的和必須是偶數(shù)。解：設(shè)an為符合題意的個數(shù)。由于1出現(xiàn)的次數(shù)與2出現(xiàn)的次數(shù)的和為偶數(shù)，可分為兩種情況：①1出現(xiàn)的次數(shù)與2出現(xiàn)的次數(shù)都為偶數(shù)；②1出現(xiàn)的次數(shù)與2出現(xiàn)的次數(shù)都為奇數(shù)。由加法法則知，序列{an}的指數(shù)母函數(shù)為(

)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)這是母函數(shù)的應(yīng)用實例之一。整數(shù)的拆分就是把整數(shù)分成若干個正整數(shù)部分，并且不考慮各部分的次序，不同的拆分方法的總數(shù)叫拆分?jǐn)?shù)P(n)。相當(dāng)于把n個無區(qū)別的球放到

1≤m≤n個無標(biāo)志的盒子中的方法數(shù)。§4.4

整數(shù)的拆分概念§4.4

整數(shù)的拆分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

整數(shù)的拆分定理4§4.4

整數(shù)的拆分定理4.4設(shè)a,b,c...為大于0

的整數(shù)，則1/[(1-xa)(1-xb)(1-xc)…]的級數(shù)展開式中xn的系數(shù)等于把正整數(shù)n拆分為a,b,c…的和的方法數(shù)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

+

...于是，每當(dāng)n可以拆分為a,b,c的和時，xn就會出現(xiàn)，這就證明了定理的結(jié)論?！?.4

整數(shù)的拆分例1例

題§4.4

整數(shù)的拆分例1、若有1克、2克、3克、4克的砝碼各一枚，問能稱出哪幾種重量？有幾種可能方案？證明：我們采用如下辦法來產(chǎn)生拆分?jǐn)?shù)的普通母函數(shù)：(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從右端的母函數(shù)知能稱出從1克到10克的重量，系數(shù)便是方案數(shù)。例如右端有2x5

項，即稱出5克的方案有2種，5=2+3=1+4。同樣6=1+2+3=2+4，10=1+2+3+4，即稱出6克的方案有2種，稱出10克的方案有1種?！?.4

整數(shù)的拆分例2§4.4

整數(shù)的拆分例2、求用1分、2分、3分的郵票貼出不同數(shù)值的方案數(shù)。1

11

1解：因郵票允許重復(fù)，故普通母函數(shù)為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為例，其系數(shù)為4，即4拆分成1、2、3之和的拆分?jǐn)?shù)為4，即

4

=

1

+1

+1

+1

=

1

+1

+

2

=

1

+

3

=

2

+

2例

題§4.4

整數(shù)的拆分例3§4.4

整數(shù)的拆分例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項的系數(shù)為5，說明稱8克的方案有5種：8

=

1

+1

+

2

+

2

+

2=2

+

2

+

4=1

+1

+

2

+

4=2

+

2

+

2

+

2=4

+

4例

題§4.4

整數(shù)的拆分例4§4.4

整數(shù)的拆分例4、整數(shù)n拆分成1,2,3,…,m的和，并允許重復(fù)，求其母函數(shù)。如若其中m至少出現(xiàn)一次，其母函數(shù)如何？解：若整數(shù)n拆分成1,2,3,…,m的和，并允許重復(fù)，其普通母函數(shù)為：若拆分中m至少出現(xiàn)一次，其普通母函數(shù)為：上式的組合意義：整數(shù)n拆分成1到m的和的拆分?jǐn)?shù)減去拆分成1到m-1的和的拆分?jǐn)?shù)，即為至少出現(xiàn)一個m的拆分?jǐn)?shù)。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

整數(shù)的拆分定義§4.4

整數(shù)的拆分定義4.3用Pk(n)表示n拆分為1,2,…,k允許重復(fù)的方法數(shù)。用Po(n)表示n拆分為奇整數(shù)的方法數(shù)。用Pd(n)表示n拆分為不同整數(shù)的方法數(shù)。用Pt(n)表示n拆分為2的不同冪（1,2,4,…）的方法數(shù)。數(shù)的拆分推論§4.4

整§4.4

整數(shù)的拆分四個推論推論4.4.1：{P3(n)}的普通母函數(shù)是1/[(1-x)(1-x2)(1-x3)]推論4.4.2：{P

(n)}的普通母函數(shù)是1/[(1-x)(1-x2)…(1-xk)]k推論4.4.3：{P(n)}的普通母函數(shù)是1/[(1-x)(1-x2)(1-x3)…]推論4.4.4：{Po(n)}的普通母函數(shù)是1/[(1-x)(1-x3)(1-x5)…]§4.4

整數(shù)的拆分定理5§4.4

整數(shù)的拆分定理4.5設(shè)a,b,c…為不同的正整數(shù)，則(1+xa)(1+xb)(1+xc)…的級數(shù)展開式中xn

的系數(shù)就是把n

拆分為a,b,c…的和，且a,b,c…最多只出現(xiàn)一次的方法數(shù)。推論4.5.1：{Pd(n)}的普通母函數(shù)為(1+x)(1+x2

)(1+x3)(1+x4)…推論4.5.2：{Pt(n)}的普通母函數(shù)是(1+x)(1+x2)(1+x4)(1+x8)…兩個推論§4.4

整數(shù)的拆分定理6-1§4.4

整數(shù)的拆分定理4.6Euler定理：Po(n)=Pd(n)等式右端正好是Po(n)的普通母函數(shù)（推論4.4.4)

。所以Po(n)=Pd(n)，即把n拆分成奇整數(shù)的和的方法數(shù)等于把n拆分成不同的整數(shù)和的方法數(shù)。2

341證明：根據(jù)推論4.5.1，Pd(n)的普通母函數(shù)為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

整數(shù)的拆分定理6-2§4.4

整數(shù)的拆分定理4.6Euler定理：Po(n)=Pd(n)可以驗證當(dāng)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

整數(shù)的拆分定理7§4.4

整數(shù)的拆分定理4.7Sylvester定理：對任意正整數(shù)n有Pt(n)=1證明I：因為任何一個正整數(shù)都可惟一地用一二進(jìn)制數(shù)來表示，而一個二進(jìn)制數(shù)又可惟一地表示成2的次冪的和，由此即得結(jié)論。上式的左端正好是Pt(n)的普通母函數(shù)（推論4.5.2),2

48,...1nnt￥

￥n=0證明II：因為序列{1,1,1,…}的普通母函數(shù)為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

整數(shù)的拆分例5§4.4

整數(shù)的拆分例

題例5、設(shè)有1,2,4,8,16,32克砝碼各一枚，試問能稱出哪些重量？分別有幾種方案？從普通母函數(shù)f(x)可以得知，用這些砝碼可以稱出從0克到63克的重量，而且辦法都是惟一的。實際是0到63的數(shù)的二進(jìn)制表示是惟一的。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