第2章母函數(shù)與遞推關(guān)系

第2章

母函數(shù)與遞推關(guān)系

2」母函數(shù)的引入

■母函數(shù)是求解計數(shù)問題的一個強有力的工具。

■其中心思想是：將一個有限或無限序列

Uo?,U19,U2，'〃"',,??

與一個函數(shù)項級數(shù)

00

(7(x)=sau(x)

n=0

聯(lián)系起來，使得我們可以通過用解析的方法研究

G(x)來得到序列叫a，……的一些性質(zhì)。

■最常用的函數(shù)項級數(shù)：

n

00,8X

G(x)=z〃x"G(X)=Z4——

〃=o""=on[

2012-9-132

2」母函數(shù)的引入

■定義2.1對于序列〃0,,稱函數(shù)

G(x)=%+%、+…+。戶”+…

為序列〃。4,…4,…的母函數(shù)。

■例序列C(〃,0),C(",")的母函數(shù)為

C(",o)+C(n,l)x+…+C(n,n)xn=(1+x)'

■例序列1,1，…，1,…的母函數(shù)為

I〃1

1+XH-???+X+?■■=--------

1-X

2012-9-133

.■2」母函數(shù)的引入

■若我們已知某個序列的母函數(shù)，通?？赏ㄟ^對母

函數(shù)的操作得到該序列的一些重要性質(zhì)。

■例對等式

C(",o)+C(")x+…+C(n.n)x"=(1+x)”

兩邊求導(dǎo)得

C(n,l)+2c(〃，2)x…+nC(n,n)xw1=n(l+x)/，-1

再令X=1便得

C(〃,l)+2co,2)+…+nC(〃，〃)=nlni

2012-9-134

2」母函數(shù)的引入

■在等式

C(n,l)+2C(n,2)x---+nC(n,n)x11=〃(1+x)w-1

兩邊同乘以X,然后再對等式的兩邊求導(dǎo)得

C(",l)x+2C(n,2)x2???+nC(nx'-nx(1+x)

C(w,l)+22C(H,2)X+???+n2C(n,n)xnl

=n(1+x)M1+n{n-1)x(1+x)/，2

C(〃，l)+22C(〃，2)+…+〃2C(〃，〃)

=/t2M1+n{n-1)2""=n{n+1)2””

2012-9-135

2」母函數(shù)的引入

■通常序列%,叫,…，〃.，…與某個問題序列p。,弋，…，々，…

的計數(shù)問題相對應(yīng)，若已知序列的母函數(shù)，則可

確定該序列，從而可以解決相應(yīng)的計數(shù)問題。

■例2.2有紅球兩只，白、黃球各一只，試求有多

少種不同的組合方案？

解所求組合方案的母函數(shù)為

22

4(x)=(l+rx+rx)(1+)(1+yx)

=l+(r+w+y)x+(J+rw+ry+wy

+(r2w+r2y+rwy)x3+(/r2wy)x4

2012-9-136

g2」母函數(shù)的引入

■如果只需要求不同的組合方案數(shù)，那么可考慮下

列母函數(shù)

2

A(x)-(1+x+x)(1+x)(l+x)

=Yl+3-x+4/x2+3?x3+x4

■所求組合方案數(shù)為：l+3+4+3+l=12o

2012-9-137

.■2」母函數(shù)的引入

■例2.3某單位有8位男同志，5位女同志。現(xiàn)要組

織一個由偶數(shù)個男同志和數(shù)目不少于兩個的女同

志組成的小組，試求有多少種組成方式？

解所求組成方式數(shù)序列的母函數(shù)為

C(x)

=(1+C(8,2)x+…+C(8,8)x)(C(5,2)x+…+C(5,5)x)

二(1+28x2+70x4+28x6+x8)(10x2+10x3+5x4+1)

=10x2+10x3+285x4+2811+8401+728x7+630x8

一.C9Y.A10-c11.1213

+350x+150x+38x+5x+x

2012-9-138

2」母函數(shù)的引入

所求的組成方式數(shù)為

10+10+285+281+840+728

+630+350+150+38+5+1

二3328

2012-9-139

q2.2母函數(shù)的性質(zhì)

?幾個常見的母函數(shù)：

■(1)----=1+X+X2+?-?+?￥”+??.

1-X

■(2)

111

?

(1-X)21-X1-X

=(1+X+X+???+*+…)(1+X+X+???+X+…)

2ti

—1+2x+3x+,,,+(n+l)x+,??

2012-9-1310

2.2母函數(shù)的性質(zhì)

■(3)

1

(1-x)M

n(n+1)2n(n+l)-(n+A-l)k

=1+nx+------x+…+-------------------------------------x+…

2!

■(4)牛頓二項式公式:

00I

(1±X)。=z(±x)

2012-9-1311

2?2母函數(shù)的性質(zhì)

00

（7）

k

k=0)

00n(-n-1)???(-n-k+1)

二z----------------------------------------(-x)

k=0k\

00

n(n+1)??一1)k

二z------x

k=0

00

k

二zX

A=0J

2012-9-1312

2.2母函數(shù)的性質(zhì)

例2.4已知GT(x)=(x4+xf5+x6+---)6?

求ak,k=0,1,2,o

角單G(x)=(x4+x5+1+…y

=[x4(l+x+—+=x24(1-x)-6

249(一6)(一6一1)…(-6-A+l)(]八

X

A=°k\

oo(A+5)(A+4)…6

=X24Z----------------------------X

Ik\

2012-9-1313

、2?2母函數(shù)的性質(zhì)

■得

"+5—24)

a=0,當(dāng)人<24時，〃=,*>24

kk*-24)

2012-9-1314

.2?1母函數(shù)的引入

-定理1.2在n個不同的元素中取r個進(jìn)行組合,

若允許重復(fù)，則組合數(shù)為C(〃+r-l,r)o

■證所求組合數(shù)的母函數(shù)為

2rn

(1+x+x+,,,+X+?,,)

n

n(n+r-

(1、r

(1-x)zX

x

U-Jr=0J

2012-9-1315

、2.2母函數(shù)的性質(zhì)

-設(shè){X.},{7為兩個序列，其相應(yīng)的母函數(shù)為A(x),

B(x)o

性質(zhì)1若

fo,k<i

bk=v

［嘰一，k>I

貝lj6(X)=xZ(X)o

2/_J//+1

S(x)=6o+bxx+bx++bi}x+bx+bi+ix+…

=o+o+...+0+%J+…

1

=x'(ao+a1x+…)=xA(x)

2012-9-1316

02?2母函數(shù)的性質(zhì)

■性質(zhì)2若無=%.,,則

r/-1,1

■證

1lxl，+}

6(x)=8。+bx+bx+…+bixx+bx+bi+ix+...

z/l+l1+2、/I

=(avxl+al+lx+a1+2x+??7?)/x

2l-\

一…一

=(\A(\x)/~ao-a1x-a2xa/-Ix7)/x

2012-9-1317

2.2母函數(shù)的性質(zhì)

z（X）

■性質(zhì)3若〃4=Z，則。（x）=

1=0X

00

bx

5(X)=Sk

A=0

=a+(a+a)x+(a+a+a)x

0v017v0127

+,,?+(u+u+u+?,,+u)x+???

\012k7

000000

=ao-yx+a1x->x+???+aAx->x+???

k=0Zr=0A=0

00z(X)

2

二(?o+?xx+a2x+…+a1+…)zi=

A=01—X

2012-9-1318

2.2母函數(shù)的性質(zhì)

00

00

■性質(zhì)4若X嘰收斂，%=Z〃，則

Ii=k

A(l)-xA(x)

5(x)=------------------------

1-X

2012-9-1319

2?2母函數(shù)的性質(zhì)

00

bx

BO)=Sk

k=0

=%⑴+(Z⑴—〃o)x+(力⑴—嘰―G)x

+…+(4(1)—uo—ai—…—a卜Jx+…

oooooo

KAxK

=/⑴2x_〃0*工x-…_ak.NE-…

4=0k=QA=0

oo

2k

=(^4(1)-aox-axx--ak1x-…壇x"

A=0

(Z⑴-xA(x))

1-X

2012-9-1320

02?2母函數(shù)的性質(zhì)

■性質(zhì)5若b4=ka卜，則B(x)=xAf(x)o

■證

k

A\x)=-(Eakx)

dxk=0

00d00

=Z----(〃A*A)=Zka卜乂

k=0dxk=l

0000

k

xA'(x)=kakx=B(x)

A=04=0

2012-9-1321

2.2母函數(shù)的性質(zhì)

a

k1X

性質(zhì)6若久貝mlIj￡(x)=-j0A{x}dx

k+1X

證

X

J。A(x)dv

0000I

xiJL

=ZJo〃戶dx=Z-------

A=0A=0A+1

0000

=Sdb*=xB(x)

4=0A=0

2012-9-1322

2.2母函數(shù)的性質(zhì)

■性質(zhì)7若g=abk+abkx+..+a/。=Ea/一，

貝ljC(x)=Z(x)6(x)，=0

■證

N(x)6(x)=(zk乙1)

i=oA=0

=E&a/J)x

k=0i=0

oo

"S=C(x)

A=0

2012-9-1323

2.2母函數(shù)的性質(zhì)

■例計算下列和式

…(n_1>

〃=ikn7

解令

(n-n(n-1>ST)

c=

a-kb-kk

kl一「l一，I—

因為〃A=Aj，由性質(zhì)5知B(x)=xCo

又嘰=AJ，由性質(zhì)5知A(x)=xBr(x)o

2012-9-1324

2?2母函數(shù)的性質(zhì)

n-1

c(X)=%+。產(chǎn)+…+c〃—戶

(〃一11(n、(n-\\

+X+???+XH-1

0J7n-1y

/.、〃-1

二(1+X)

C(x)=(n-1)(1+x)n~2

"-3

C〃(x)=(〃一l)(n-2)(1+x)

2012-9-1325

2.2母函數(shù)的性質(zhì)

A(x)=xB\x)=x[C"(x)+xC,r(x)]

=x[(n-1)(1+x)n2+x(n-1)(n-2)(1+x)M3]

=x(n-1)(1+x)n~2+x\n-1)(?-2)(1+x)””

(n-\\

2

%⑴=乎

2<k)

=5—1)2""+(w-1)0-2)2"3=_I)?""

?-2An-1A

fk，=n(n-1)2""—(%_l)2

k

2012-9-1326

習(xí)題

■1.9試證《的正除數(shù)的數(shù)目是奇數(shù)。

證當(dāng)廿1時，結(jié)論顯然正確。

當(dāng)〃>1時，設(shè)n的因子分解為〃=p：

2a,2a,

n=PlPl…Pk

所以N的正除數(shù)的數(shù)目是

々。，+（奇數(shù)

（21+1.1）（2X1）…2K%,+1）=

2012-9-1327

0習(xí)題

-L16n個完全一樣的球，放到r個有標(biāo)志的盒子

(n^r)中，無一空盒，試問有多少種方案？

-解先將r個分別放入r個盒子，然后再將剩余的n-

r個球任意地放到|?個盒子中，所求方案數(shù)為

(rn-r-(n-(n-

2012-9-1328

0習(xí)題

-解2所求組合方案的母函數(shù)為

/2kr

（X+X+…+x+?一x）

/11r-n

=X--------=x(1—x)=XzX

J_X'/1=0\J

00/n-1、\

2。、“/…M-1

2012-9-1329

■習(xí)題

■L276位男賓，5位女賓圍一圓桌而坐，

(a)女賓不相鄰有多少種方案？

(b)所有女賓在一起有多少種方案？

(c)一女賓A和兩位男賓相鄰又有多少種方案？

解(a)先讓6位男賓圍圓桌坐下，有5!種方案,

再將5位女賓插入到男賓之間，有種

65432=6!

方式，所以共有5!6!種方案。

2012-9-1330

?習(xí)題

■(b)將5位女賓視為一人，與6位男賓圍圓桌坐下,

有6!種方案，考慮到女賓之間的次序，共有6!5!

種方案。

■(c)從6位男賓中任取兩人，其方案數(shù)為C(6,2),

對于任何取定的兩位男賓，將A插入到這兩位男

賓之間，有2種方案，將這兩位男賓與A視為一人,

與其他人圍圓桌坐下，有8!種方案，所以共有

2c(6,2)8!種方案。

2012-9-1331

習(xí)題2

■2.12.42.62.48

2012-9-1332

2.3整數(shù)的拆分

■所謂整數(shù)的拆分是把一個正整數(shù)n表示成若干個

正整數(shù)的和，而這些正整數(shù)的次序是無關(guān)緊要的。

例5,4+1,3+2,3+1+1,2+2+1,2+1+1+1,

1+1+1+1+1是整數(shù)5的7個不同的拆分。

在整數(shù)的拆分表示〃=%+勺+…中，常使

nv>n2>..>nk

不同拆分的總數(shù)稱為拆分?jǐn)?shù)，通常用P(〃)表示n

的拆分?jǐn)?shù)。

2012-9-1333

2.3整數(shù)的拆分

■例求(1+1+，蘆中項1°的系數(shù)。

解項X20有以下三種生成方式：

①mu=一°：有C(100,5)種選取方法。

②=.有c(ioo,1)C(99,3)種選取

方法。

③=”:有C(100,2)C(98,1)種選取方法。

所以項x20的系數(shù)為：

C(100,5)+C(100,1)0(99,3)+C(100,2)C(98,1)

2012-9-1334

2.3整數(shù)的拆分

■例2.10若有1克、2克、3克、4克的祛碼各一枚,

問能稱出哪幾種重量？有幾種可能的方案？

解其母函數(shù)為

234

(1+x)(l+X)(1+X)(1+X)

=1V+x+x2+_2x3+_2x4+02x5+_26x

A78910

+2x+x+x+x

知能稱出1到10克的重量，系數(shù)為方案數(shù)。

譬如有5=4+1=3+2,6=4+2=3+2+1。

2012-9-1335

j2.3整數(shù)的拆分

■例2.11求用1角、2角、3角的郵票可貼出不同數(shù)

值郵資的方案數(shù)的母函數(shù)。

解因郵票允許重復(fù)，故其母函數(shù)為

(1+x+x+,,,)(1+x+x+,,,)(1+x+x+…)

1-X1-X1-X1-X-X+X+X-X

=1v+x+02x2+-33x+4.x4+.55x_+76x+…

由x4的系數(shù)為4知，用1角、2角、3角的郵票貼出

數(shù)值4的方案數(shù)為4。

2012-9-1336

2.3整數(shù)的拆分

■例2.12若有1克的祛碼3枚，2克的4枚，4克的2

枚。問能稱出哪些重量？各有幾種方案？

G(x)

23246848\

=(1+X+X+X)(1+X+X+X+X)(1+X+X)

=1<+x+.2x2+—2x3+—3x4+—3x5+4/x6+4x7

89101141213

+5x+5x+5x+5x+4x+4Ax

+3_x14+3-1x5+-2x16+—2x17+x18+X19

2012-9-1337

2.3整數(shù)的拆分

■例2.13整數(shù)n拆分成1,2,3,…,m的和,并允許重

復(fù)，求其母函數(shù)。若m至少出現(xiàn)一次，其母函數(shù)

如何？

解其母函數(shù)為

GJx)

=(1+X+X2+???)(1+X2+X4+???)???(1+x，w+x2zM+???)

1111

1-X1-X21-xm(1-x)(l-X2)(1-x，H)

2012-9-1338

—2?3整數(shù)的拆分

J----—

■若m至少出現(xiàn)一次，其母函數(shù)為

G/x)

=(l+x+x+,,,)(1+x+x+??,)??,(x+x+?,,)

1-X1-X21-xn(1-x)(l-X2)(1-)

11

(1-x)(l-X2)-(1-x/H)(1-x)(l-X2)(1-x'l)

2012-9-1339

q2.3整數(shù)的拆分

■「列2.15設(shè)有1、2、4、8、16、32克祛碼各一枚，

試問能稱出哪些重量？分別有幾種方案？

G(x)=(1+x)(l+x2)(1+x4)(l+x8)(1+x]6)(l+x32)

.24.8.1632.64

1-x1-x1-x1-x1-x1-X

?????

2481632

1-x1-x1-x1-x1-x1-X

64

1—X263

=------=(1+X+X+???+、)

1—X

用這些祛碼可以稱出從1克到63克的重量，而且

方案是唯一的。

2012-9-1340

2.3整數(shù)的拆分

■定理2.1正整數(shù)n拆分成不同整數(shù)之和的拆分?jǐn)?shù)等

于拆分成奇整數(shù)之和的拆分?jǐn)?shù)。

證設(shè)〃〃表示n拆分成不同整數(shù)之和的拆分?jǐn)?shù)，則

序列｛%｝的母函數(shù)為

G(x)=(1+x)(l+x2)(1+x3)(1+x4)???

1-x21-x41-x61-x8

3^2??????

.1-x.1-x21-x3.1-X4

1111

2012-9-1341

■.2.3整數(shù)的拆分

—---

■定理2.2n拆分成其重復(fù)數(shù)不超過2的數(shù)的和，其

拆分?jǐn)?shù)等于它拆分成不被3除盡的數(shù)的和的拆分

數(shù)。

證｛aj的母函數(shù)為

G(x)

=(1+X+X2)(1+X2+X4)(1+X3+X6)(1+X4+X8)???

36912

1-X?1-X?1-X?1-X???

1-X1-X21-X31-X4

1111

??????

1Y-XY1-X2.1-X4.1-X5

2012-9-1342

2.3整數(shù)的拆分

定理2.3n拆分成其重復(fù)數(shù)不超過k的數(shù)的和，

其拆分?jǐn)?shù)等于它拆分成不被k+1除盡的數(shù)的和的

拆分?jǐn)?shù)。

2012-9-1343

2.4Ferrers圖象

■Ferrers圖象：一^從上而下的n層格子，j為第i

層的格子數(shù)。當(dāng)n.>ni+i(i=1,2,???,n-1)時，即上

層的格子數(shù)不少于下層的格子數(shù)時，稱之為

Ferrers圖象。

■整數(shù)的一個拆分可以用一個Ferrers圖象來表示,

圖象中的每一行對應(yīng)于拆分的一部分。

■例整數(shù)14的拆分6+3+3+2可以用下列Ferrers圖

象來表示

2012-9-1344

,2.4Ferrers圖象

■Ferrers圖象的性質(zhì)：

■每一層至少有一個格子；

■第一行與第一列互換，第二行與第二列互換，…，

所得到的圖象仍然是Ferrers圖象，這兩個Ferrers

圖象稱為是一對共聊的Ferrers圖象。

2012-9-1345

2.4Ferrers圖象

■利用Ferrers圖象可得到關(guān)于整數(shù)拆分的一些性質(zhì)。

(1)整數(shù)n拆分成最大數(shù)為k的拆分?jǐn)?shù)和數(shù)n拆分成k

個數(shù)的和的拆分?jǐn)?shù)相等。

(2)整數(shù)n拆分成最多不超過k個數(shù)的和的拆分?jǐn)?shù)和n

拆分成最大數(shù)不超過k的拆分?jǐn)?shù)相等。

2012-9-1346

2.4Ferrers圖象

■由(2)知，拆分成最多不超過m個數(shù)的和的拆分?jǐn)?shù)

的母函數(shù)為

1

(1-x)(l-X2)(1-xm)

■正好拆分成m個數(shù)的和的拆分?jǐn)?shù)的母函數(shù)為

11

(1-x)(l-X2)(1-x，M)(1-x)(l-X2)(1-

2012-9-1347

2.4Ferrers圖象

■(3)整數(shù)n拆分成互不相同的若干奇數(shù)的和的拆分?jǐn)?shù),

和n拆分成有自共聊的Ferrers圖象的拆分?jǐn)?shù)相等。

設(shè)

構(gòu)造十d圖象；+般A-彳物第一列都是,

格，第二行，第二列都是格，…，第k行，+第

k列都是格，這樣所得的Ferrers圖象是自共

聊的。反龍;亦然。

2012-9-1348

2.4Ferrers圖象

■例17=9+5+3所對應(yīng)的Ferrers圖象為

瞪

2012-9-1349

2.6指數(shù)型母函數(shù)

回題：設(shè)有n個元素，其中式素%重復(fù)了%次，

元素〃2重復(fù)了%次，…，元素〃A重復(fù)了巴次，

%+%+.?.+%=〃,從中取r個排列，求不同的

排列數(shù)。

2012-9-1350

2.6指數(shù)型母函數(shù)

■XE理設(shè)S={%〃[,〃2〃2,…，〃A"A}為一多重集，其

中〃+〃+...+：1；，那以從s中取n個元素的

排列?數(shù)為2A

■證排列的個數(shù)為

n???

C(n,nt)C(n-%,巴)…C(n-ni-2

2012-9-1351

2.6指數(shù)型母函數(shù)

■例2.168個元素中勺重復(fù)了3次，心重復(fù)了2次，

%重復(fù)了3次，從中取r個，設(shè)其組合數(shù)為。一則

。。，*，。2，，一，。8的母函數(shù)為

G(x)=(1+x+x2+x3)(l+x+x2)(l+x+x2+x3)

?g,2八3＜八4,6-7

=l+3x+6x+9x+10x+9x+6x+3x+x

由x4的系數(shù)為10知，從這8個元素中取4個組合，

其組合數(shù)為10。這10個組合是如何構(gòu)成的呢？考慮

2012-9-1352

2.6指數(shù)型母函數(shù)

23223

('1+X1+X1+X1八)(1+X2+X2八)(1+X3+X3+X3"7)

=…++…)+…

其中項X產(chǎn)；表示1個〃「3個心。而由1個名,3

?3個所組成排列的個數(shù)為

4

4!4!x

---=>---?—

1!3!1!3!4!

2012-9-1353

2.6指數(shù)型母函數(shù)

■定義對于序列稱函數(shù)〃。，〃1,n

n

xX

G(x)=a+a——+…+〃----十…

0011!n!

為序列的指數(shù)型母函數(shù)。

■例2.17序列1,1,1,…，1,…的指數(shù)型母函數(shù)為

2

XX

1+——++…=e

1!2!

2012-9-1354

2.6指數(shù)型母函數(shù)

■例2.18序列0!,1!,2!,…，k!,…的指數(shù)型母函數(shù)

為

2

xx1

0!+1!—+2!+…=1+x+x2+???=

1!2!1-x

2012-9-1355

2.6指數(shù)型母函數(shù)

■例2.20證明序列1,1「3,1.3.5,1.3.57,…的指

3

數(shù)型母函數(shù)為(l-2x)2\

2012-9-1356

2.6指數(shù)型母函數(shù)

(3、

300

2(-2x)z

(1-2x)二z2

r=0

r7

3f3A(3、

―—―F+1

oo

212JI27'—rr

二z2x

r=0

352r+1

00.

l222、，

二S-------------------2xz[1?3?5?…(2r+1)]

r=0r!

2012-9-1357

2.6指數(shù)型母函數(shù)

■7E理設(shè)S=｛%%,〃2方2,?,，”A〃A｝為一多重集，其

中％+%+…+nk=n?并設(shè)a=0,1,2,...)為S

的由列：則｛J｝的指數(shù)型母函數(shù)為：

G(x)=

/n1\/n2\Znk

XXXXXX

1++…+1++…+…1++…+

I1!%!八1!巴DI1!乙!

2012-9-1358

2.6指數(shù)型母函數(shù)

■例2.22由a,b,c,d這4個符號取5個進(jìn)行排列，要

求〃出現(xiàn)的次數(shù)不超過2次，但不能不出現(xiàn)；b出

現(xiàn)的次數(shù)不超過1次；c出現(xiàn)的次數(shù)不超過3次，可

以不出現(xiàn)；d出現(xiàn)的次數(shù)為偶數(shù)。求滿足上述條件

排列的個數(shù)。

解設(shè)滿足上述條件的r排列的個數(shù)為p,個，序列

PI，P2,…，的指數(shù)型母函數(shù)為

2012-9-1359

2.6指數(shù)型母函數(shù)

2\224

'XXXXX

G,(x)=一+(1+x1+—+---+++一

I1!2"1!2!2!4!7

2346

xXXX

一+5——+18——+64—+215十645——

1;2!3!4;6!

78910

XXXX

+1785—+140—+7650——+12600

7!8!9!10!

■故所求排列的個數(shù)為215。

2012-9-1360

2.6指數(shù)型母函數(shù)

■例2.23求1,3,5,7,9這5個數(shù)字組成的n位數(shù)的個

數(shù)，要求其中3,7出現(xiàn)的次數(shù)為偶數(shù)，其它數(shù)字

出現(xiàn)的次數(shù)不加限制。

解設(shè)滿足條件的r位數(shù)的個數(shù)為勺，則｛〃，｝對應(yīng)的

指數(shù)型母函數(shù)為

23

/X2X4'XX2X3、

G/x)=1+++…1+—+++…

I2!4!I1!2!3!

2012-9-1361

2.6指數(shù)型母函數(shù)

(1、1x23

/X7、/x、3/X-X

一(e+e)(e)=-(6+e)e

(2)4

12x一一2x、3x1/5x-3xx、

~(ze+2+e)e(?+2e+e)

44

-S-x"+2X—一+I—x

41"=o"！?=on\"=o/i!

100/、x

二-Z(5"+2.3〃+1)—

4w=0n!

1

所以nn

an=~(5+2-3+1)

4

2012-9-1362

習(xí)題

■2.112.122.50

2012-9-1363

2.6指數(shù)型母函數(shù)

■例2.24設(shè)為7個有區(qū)別的球，將它們放進(jìn)4個有標(biāo)

標(biāo)志的盒子，要求1,2兩盒必須含偶數(shù)個球，第3

盒含奇數(shù)個球，問有多少種不同的分配方案？

解

31242141234

設(shè)將r個有區(qū)別的球放進(jìn)4個有標(biāo)志的盒子的方案數(shù)

為W,那么序列｛〃，｝的指數(shù)型母函數(shù)為

2012-9-1364

2.6指數(shù)型母函數(shù)

2

4352、

xXxXXxX

+---++一十---++…1+一+---+???

11!

2!)3!5!)1!2!

1

X

一X、(X一*、

e+ee

一_X\

/2x—2M、/X

一(e+2+e)(e)e

8

2J27

r

1/4x2x100

-2xrrX

一(e+ee1)=-E【4+2-(-2)]—

88r=lrI

1

77-(-2)7

所求方案數(shù)為。74+2=2080

8

2012-9-1365

2.6指數(shù)型母函數(shù)

■例2.25r個有標(biāo)志的球，放進(jìn)n個不同的盒子，

要求無一空盒，問有多少種不同的分配方案？

解這相當(dāng)于n個有標(biāo)志的對象取r個作允許重復(fù)的

排列，且每個對象至少出現(xiàn)一次。

設(shè)排列數(shù)為。一則序列｛〃,｝的指數(shù)型母函數(shù)為

e/n

G(x)=x+——+——+=(?、—1)”

I2!3!

2012-9-1366

2.6指數(shù)型母函數(shù)

nA

-El

k=0IkJ

■故

a,=A)

k=。l4J

2012-9-1367

2.7遞推關(guān)系舉例

■例2.26Hanoi塔問題。

HABc

2012-9-1368

2.7遞推關(guān)系舉例

■算法的分析：設(shè)的為將n個圓盤從塔座A移動到

塔座B上所需要的移動次數(shù)，則有

hn=2n〃-1i+ln>1

儲=111=1

h=2h+1=2(2h2+D+

角星法Lnn-\An-L/1

21

=2hn-2,+2+11=2〃一3(24J,+1)+2+1

32

=2hn-3,+2+2+1

n-1-n-20y.

—2h+2+???+2+1=2—1

2012-9-1369

修2?7遞推關(guān)系舉例

■解法2：用母函數(shù)求解

2

H(x)htx+h2x+---+hnx"+■-

2n

-2xH(X)=-2fllX---------2hn-lX+…

2n*

(l-2x)H(x)=x+x+??-+x+…=---------

1—X

X「1118

H(X)=-----------------------=--------------------=y(2〃-l)x

(1-x)(l-2x)[1-2x1-xJ工

h(n)=2-1

2012-9-1370

2.7遞推關(guān)系舉例

■例2.28求n位十進(jìn)制數(shù)中出現(xiàn)偶數(shù)個5的數(shù)的個數(shù)。

解設(shè)二n位十進(jìn)制數(shù)中出現(xiàn)偶數(shù)個5的數(shù)的個