2

/27生成函數(shù)表示序列的一種有效方法就是生成函數(shù),它把序列的項作為一個形式冪級數(shù)中變量x的冪的系數(shù).求解許多類型的計數(shù)問題在各種限制下選取或分配不同種類物體的方式數(shù)使用不同面額的硬幣換一

的方式數(shù)等求解遞推關系先把關于序列的項的遞推關系轉換成涉及生成函數(shù)的方程然后求解這個方程得到生成函數(shù)找到生成函數(shù)的冪級數(shù)的系數(shù),從而求解了原來的遞推關系證明組合恒等式研究序列的許多性質,例如建立關于序列的項的漸進公式3

/27生成函數(shù)的定義定義實數(shù)序列a0,a1,a2,…,ak,…的生成函數(shù)是無窮級數(shù)k

0當用生成函數(shù)求解計數(shù)問題時,通常將它們考慮成形式冪級數(shù),這里忽略了這些級數(shù)的收斂問題.但是為了應用某些微積分的結果,考慮冪級數(shù)對什么

x收斂有時是很重要的.k

ka

xG(

x)

a

a x

a

xk

0

1

k4

/27生成函數(shù)的性質定理令,那么注:上述定理只有當冪級數(shù)在一個區(qū)間內收斂時才有效.但是,生成函數(shù)的定理并不局限于這種級數(shù).在級數(shù)不收斂的情況下,上述定理中題可以看成是生成函數(shù)和與積的定義.k

0kkk

0kkb

xg(

x)

a

x

,f

(

x)

k

0k

kf

(

x)

g(

x)

(a

b

)xkk

kk

0

j

0f

(

x)g(

x)

ajbk

j

x5

/27二項式系數(shù)為了用生成函數(shù)求解許多重要的計數(shù)問題,需要在指數(shù)不是正整數(shù)的情況下應用二項式定理.定義設u是實數(shù)且k是非負整數(shù),

那么

二項式系數(shù)

定義為定理

二項式定理設x,y是實數(shù),

|x/y|<1,

u是實數(shù),那么

1,k

0k

0k!

k

u

u

u

u k

11)()(k

0

k

uku

x

yk

u(

x

y)

6

/27常用公式z是實數(shù),|z|<1nn

mzn0n

m

n

1

(1)

(1

z)nnmzn0

m

n

1(1

z)

zn

n

n02

122n

(1)n

2n(1

z)

zn1

n

1

n22n1

(1)n1

2n

2(1

z)2

1

n17

/27常用的生成函數(shù)nknk2

211

x

x

n

n

nk

0

k12

n

1

nx

1

x

xk

1

2

n

k

1k

0

(1

x)nk1k

0xk

ex!!1k!k

0)kk

0

(1)k

18

/27由序列求生成函數(shù)例(1)an

7

3

,

(2)a

n(n

1)nnn

(xG

n0n0(2)G(

x)

n(n

1)xnn1

n1x

G()x

dx

nxn1

x2

H

(

x),

H

()x

nxn10x

()xHdxn0

xn1

0x 11

x (1

x)2

H

(

x)

0x2x

G(

x)dx

(1

x)2322

xx2(1

x)(1

x)

G(

x)

9

/27由生成函數(shù)求序列通項求an例{an}的生成函數(shù)為解x

3

xn0

2n1

xn2

3

2n

17,

n

1

a

2n1

,n

2(2x)n

3xn010

/

27計數(shù)問題與生成函數(shù)生成函數(shù)可以用于求解各種計數(shù)問題.計數(shù)各種類型的組合數(shù).前面介紹了計數(shù)n元集合的允許重復的r組合數(shù),在這些組合中可能存在某些附加的約束.這種問題與計數(shù)形如方程x1+x2+…+xn=C的解是等價的,其中C是常數(shù),每個xi是可能具有某些約束的非負整數(shù).11

/

27不定方程解的個數(shù)基本模型

x1+x2+…+xk

=

r

,

(r,xi為自然數(shù))設方程的解的個數(shù)為sr,

得到序列{sr}r∈N則sr

=ar

,

r∈N設x1=t1,x2=t2,…,xk=tk

是方程的一個解,則t1+t2+…+tk

=rr

0r

ra

yG(

y)

(1

y

y2

)k

y

t1ytk

yry

t2yt1

t2

tk(1

y

y2

)(1

y

y2

)(1

y

y2

)12

/

27不定方程解的個數(shù)續(xù)基本模型

x1+x2+…+xk

=

r

,

(r,xi為自然數(shù))設方程的解的個數(shù)為sr,

得到序列{sr}r∈N則sr

=ar

,

r∈Nk1r

2ar

y

G(

y)

(1

y

y

)

(1

y)kr

0r

0r!

(k)(k

1)(k

r

1)

r(

y)

r

0(1)r

yrr!

(1)r

(k

)(k

1)(k

r

1)

r

0

r

yr

k

r

1r

sr

ar

k

r

113

/

27不定方程解的個數(shù)續(xù)擴展模型(帶限制條件)ni21

k

,

ylk

1

ynk

)xi

NG(

y)

(

yl1

yl1

1

yn1

)

(

yl2

yl2

1

yn2

)

(

ylk擴展模型(帶系數(shù))p1

x1

p2

x2

pk

xk

r,

y2

p1G

y

((1)

y

p1

)

)

y2

pk

(1

y

p2

)

(1

y

pk

y2

p214

/

27例例求e1+e2+e3=17的解的個數(shù),其中ei是非負整數(shù),滿足2≤e1≤5,

3≤e2≤6,4≤e3≤7.解具有上述限制的解的個數(shù)是(y2+y3+y4+y5)

(y3+y4+y5+y6)(y4+y5+y6+y7)的展開式中y17的系數(shù).計算可得在這個乘積中的x17的系數(shù)是3.

因此,上面的不定方程有3個解.(注意,計算這個系數(shù)與枚舉方程的具有給定約束的所有解幾乎要做同樣多的工作.但是這種方法常?？梢杂糜谇蠼飧鞣N各樣的具有特殊規(guī)則的計數(shù)問題.此外,可以用計算機代數(shù)系統(tǒng)做這種計算.)15

/

27例例1克砝碼2個,2克砝碼1個,4克砝碼2個,問能稱出哪些重量,方案有多少?解重量0123456789101112方案11212121212111

2321G(

y)

(1

y

y2

)(1

y2

)(1

y4

y8

)

1

y

2

y2

y3

2

y4

y5

2

y6

y7

2

y8

y9

2

y10

y11

y12ryr的系數(shù)7例例

把價值1

,

2價值k幣 是有序的和無序+…)(1+x5+x10+…)5)2

+…中xk的系數(shù),恰好n個代幣產(chǎn)生投幣6 的情況:無序

5種方法有序

15種方法解無序:(1+x+x2+…)(1+中xk

的系數(shù)0+6+0表示3個2,1個5,2個2,1個21+0+5表示1個12+4+0表示2個14+2+0表示4個16+0+0表示6個1合計5種方法個代幣:{1,5}的全排列數(shù)P(2,2)=2的某種物品3個代幣:{2,2,2}的全排列數(shù)14個代幣:{1,1,2,2}的全排列數(shù)4!/(2!2!)=65個代幣:{1,1,1,1,2}的全排列數(shù)5!/4!=56個代幣:{1,1,1,1,1,1}的全排列數(shù)1合計15種方法17

/

27使用生成函數(shù)求解多重集的r組合多重集S={n1a1,n2a2,…,nkak}的r組合數(shù)是不定方程

x1+x2+…+xk

=r,xi≤ni

(i=1,2,…,k)

的非負整數(shù)解的個數(shù)生成函數(shù)G(

y)

(1

y

yn1

)(1

y

yn2

)(1

y

ynk

)特別地,當r≤ni

(i=1,2,…,k)G(

y)

(1

y

yr

)(1

y

yr

)(1

y

yr

)的展開式中yr的系數(shù)為C(r+k–1,r)18

/

27使用生成函數(shù)求解遞推關系解+例

an

5an1

6an2

0,

a0

1,

a1

2

5

xG(

x)

6x2G(

x)

G(

x)

5

2n

xn

4

3n

xnn0

n0

x

an

5

2

4

3n

n

5a

x3

5a

x4

2

3

6a

x3

6a

x4

1

23a0

a1

x

a

x2

2

5a0

x

5a

x216a

x20G(

x)

a x3

(1

5x

6x2

)G(

x)

a0

(a1

5a0

)xh1

1h

h

,

n

2h

n1k

1k

nkn例n1nnh

x解

H

(

x)

2l

1llk

1kkh

xh

xH

(

x)

n1k

1k

nknh

hxn

1

H

(

x)

x2n22211

(1

4x)H

(

x)

1n2221

1

(1hx4nx)2

H(x)

hx該解舍去,因為

當x=0,H(x)=0211

(1

4x)2H

(

x)

1H

(

x)

1H1n2111n(4x)x3nn(4x)

(2n

3)

2

4

(2n

2)

(

(n(4

x)2n1)2)(!

n

1)(x1)1

1

0

(2n

3)

2

(

4

x)n

((44xx))n2n

22

nn211

(1n()n021)2nnnn2n1nn!

1

13

1

1112nx

(4

x)2n

22

nn211

n

(n1)n1n12nn1n!2

4

(2n

2)2

2

1

12n

2n

2nn1

(n111

)n

22n

n(n

n1!)!(n

1)!h

n20

/

27練習計數(shù)堆棧的輸出計數(shù)1,2,…n放入堆棧后的不同的輸出個數(shù).解在1進棧到出棧之間作為一個子問題,1出棧后作為一個子問題.過程如下:1進棧;處理k個數(shù)(2,…,k+1)的進棧問題;1出棧;處理k+2,…,n的進棧問題.T

(k)T

(n

1

k),

n

2T

(n)

n1k

021

/

27計數(shù)堆棧的輸出遞推方程求解kn)TT

1)1(,1)0(n1k

0l

0k

0G2

(

x)

T

(kk

0n1Txn1n1n1T

(n)x

G(

x)

1xG2

(

x)

G(

x)

1

01

x

n

x

2nn

1

n

2xG(0)

01

1

4xG(

x)

1n0n0nT

(n)xG(

x)

2nn

1

n

1T

(n)

22

/

27指數(shù)生成函數(shù)定義設{an}為序列,稱n為{a}的指數(shù)生成函數(shù).n0n!xnGe

(

x)

ann0n0men!xnxn

P(m,

n)n!(m

n)!m!G

(

x)

(1

x)

n0nn0

nmx

C(m,

n)xn

m

G(

x)

(1

x)

23

/

27多重集r排列的指數(shù)生成函數(shù)每一個解對應S的一個

r

組合該r

組合產(chǎn)生的

r排列(全排列)數(shù)1

2(

x)

ffknnne(

x)

f

(

x)S

{n1

a1

,

n2

a2

,,

nk

ak

}

G

(

x)

inin

!!21)(,,k2i

1nk2!!n12!!Ge

(

x)11

2

kxm1

xm2

xmkn

r

0

m

m

m

r

m1!

nk

xrkr

012m2

!

mk

!r!

12

mmmr!m!!m!

m

r24

/

27例例由1,2,3,4組成的五位數(shù)中,要求1出現(xiàn)不超過2次,但不能不出現(xiàn),2出現(xiàn)不超過1次,3出現(xiàn)可達3次,4出現(xiàn)偶數(shù)次.求這樣的五位數(shù)個數(shù).例紅,白,蘭涂色1×n的方格,要求偶數(shù)個為白色,問其方案數(shù)?

!2

x

11Ge

(

x)!2

!3

!4

!52

3

4xx

5

18

64

215

24

22!4!

2!2

Gex()12221

e1

1

n0

3n2

n02n0

3n

1

xn2

n!n!xnn!xn解確定序列{an}的生成函數(shù),

其中

an

C(n,3)63n0nn0

nn(n

1)(n

2)x

x

n

1G(

x)

6

6n0

1

x3

n(n

1)(n

2)xn3

1

x3

A(

x)x

xn00

n0