離散數(shù)學(xué)2代數(shù)結(jié)構(gòu)與組合課件chapter

生成函數(shù)的定義牛頓二項(xiàng)式定理生成函數(shù)的性質(zhì)生成函數(shù)與序列的對(duì)應(yīng)關(guān)系第三節(jié)生成函數(shù)及其性質(zhì)設(shè)序列{an}，構(gòu)造形式冪級(jí)數(shù)G(x)

=

a0

+

a1x

+

a2x2

+

…

+

anxn

+

…稱G(x)為{an}的生成函數(shù).實(shí)例：{C(m,n)}的生成函數(shù)為G(x)=

1

+

C(m,1)x

+

C(m,2)x2

+

…

=

(1+x)m給定正整數(shù)k,{kn}的生成函數(shù)為G(x)

=

1+

kx

+

k2x2

+

k3x3

+

…

=

1

1-kx生成函數(shù)的定義牛頓二項(xiàng)式系數(shù)：設(shè)r為實(shí)數(shù)，n

為整數(shù)，

=

1

0n!

r(r

-

1)...(r

-

n

+

1)n

<

0n

=

0n

>

0

n

r

牛頓二項(xiàng)式定理設(shè)a為實(shí)數(shù)，則對(duì)一切x,y，|x/y|<1

有n

n!n=

(

x

+

y)

=￥

a

a

a(a

-

1)...(a

-

n

+

1)n=0

n

a-nax

y

,

其中牛頓二項(xiàng)式定理當(dāng)a

=m時(shí)，變成二項(xiàng)式定理

n=0

n

m-nmx

y

,n￥

m

(

x

+

y)

=

n=0

nmz

,n￥

m

(1

+

z)

=na(a

-

1)...(a

-

n

+

1)

=n

n!

a

(

x

+

y)

=￥

a

n=0

xn

ya-n

,a其中牛頓二項(xiàng)式定理（續(xù)）1=(-1)=￥|

z

|<

1zn￥

m

+

n

-

1(1

-

z)(1

-

z)

=|

z

|<

1zn(1

+

z)1(1

+

z)

=n=0nm-mnn=0n

m

+

n

-

1m-m￥=1n=0n(n

+

1)

x(1

-

x)2m

=

2,=

1

+

x

+

x

2

+

...1

-

x1m

=

1,當(dāng)a

=-m

時(shí)，=

n

=

=n

n

n

m

+

n

-

1=

(-1)

n!(-1)n

m(m

+

1)...(

m

+

n

-

1)n!

a

-

m

(-m

)(-m

-

1）...(

-m

-

n

+

1)二項(xiàng)式定理（續(xù)）線性性質(zhì)：bn=aan,

則B(x)=aA(x)cn=an+bn,

則C(x)=A(x)+B(x)乘積性質(zhì)：n3．

cn

=

aibn-i

,i

=0則C

(

x)

=

A(

x)

B(

x)生成函數(shù)的性質(zhì)（線性與乘積）ann

?

ln

<

l,04．

b

=n-l則B(x)=xl

A(x)a0

,

a1

,

...

,

an

,

...0,0,...,0,

bl

,

bl

+1

,

...,

bl

+n

,...l個(gè)05．bn=an+l

,則xll

-1A(

x)

-

an

xnB(

x)

=

n=0

a0

,

a1

,

...

,

al

,

al

+1

,

...b0

,

b1

,

...生成函數(shù)的性質(zhì)（移位）nA(

x)6．

bn

=

ai

,

則

B(

x)

=

1

-

x1+

...1

-

x1

-

x1

10

1

-

xB(

x)

=

a+

a

x

+

...

+

a

xn1

ni

=0b0

=

a0b1

x

=

a0

x

+

a1

x...bn

xn

=

a0

xn

+

a1

xn

+

...

+

an

xn...iin7．

b

=￥￥i

=n

A(1)

-

xA(

x)1

-

xn=0a

收斂，則B(x)=a

,

且A(1)=生成函數(shù)的性質(zhì)（求和）換元性質(zhì)：bn=anan,

則B(x)=A(ax)求導(dǎo)與積分性質(zhì)：bn=nan,

則B(x)=xA’(x)n10．b

=n

+

1an01

x,

則B(x)=x

A(x)dx生成函數(shù)性質(zhì)（換元、微積分）1．

給定序列{an}或關(guān)于

an

的遞推方程,

求生成函數(shù)

G(x)利用級(jí)數(shù)的性質(zhì)和下述重要級(jí)數(shù)￥￥￥￥￥￥==1=

1

+=

1

+

1k

=1k2k

-1kk

=1k

=1kk

=1n=0nn=0xk

-

1(-1)k

-1

2k

-

22

kx

=

1

+(-1)k

-1

(2k

-

2)!2k

k!

2k

-1

(k

-

1)!x2k

k!(-1)k

-11

3 5...(2k

-

3)k!￥

1

1

(

1

-

1)...(

1

-

k

+

1)k

=0

k

(1

+

x)

2

=

2

xk

=

1

+

2

2

2

xk(-1)n

x1

+

xxn1

-

x1生成函數(shù)與序列的對(duì)應(yīng)例

1

求序列{an}的生成函數(shù)（1）an

=

7

3n

（2）an

=

n(n+1)n

n

n71

-

3

x3

x

=

7

(3

x)

=解：（1）

G(x)=7

￥

￥n=0

n=0200012

xx2xxxxxG(

x)

=

(

)'=(1-

x)2

(1-

x)3(1-

x)G(

x)dx

=H

(

x)

=(1-

x)2=

1-

x

,H

(

x)dx

=