离散组合数学2生成函数

2

/27生成函数表示序列的一种有效方法就是生成函数,它把序列的项作为一个形式幂级数中变量x的幂的系数.求解许多类型的计数问题在各种限制下选取或分配不同种类物体的方式数使用不同面额的硬币换一

的方式数等求解递推关系先把关于序列的项的递推关系转换成涉及生成函数的方程然后求解这个方程得到生成函数找到生成函数的幂级数的系数,从而求解了原来的递推关系证明组合恒等式研究序列的许多性质,例如建立关于序列的项的渐进公式3

/27生成函数的定义定义实数序列a0,a1,a2,…,ak,…的生成函数是无穷级数k

0当用生成函数求解计数问题时,通常将它们考虑成形式幂级数,这里忽略了这些级数的收敛问题.但是为了应用某些微积分的结果,考虑幂级数对什么

x收敛有时是很重要的.k

ka

xG(

x)

a

a x

a

xk

0

1

k4

/27生成函数的性质定理令,那么注:上述定理只有当幂级数在一个区间内收敛时才有效.但是,生成函数的定理并不局限于这种级数.在级数不收敛的情况下,上述定理中题可以看成是生成函数和与积的定义.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二项式系数为了用生成函数求解许多重要的计数问题,需要在指数不是正整数的情况下应用二项式定理.定义设u是实数且k是非负整数,

那么

二项式系数

定义为定理

二项式定理设x,y是实数,

|x/y|<1,

u是实数,那么

1,k

0k

0k!

k

u

u

u

u k

11)()(k

0

k

uku

x

yk

u(

x

y)

6

/27常用公式z是实数,|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常用的生成函数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由序列求生成函数例(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由生成函数求序列通项求an例{an}的生成函数为解x

3

xn0

2n1

xn2

3

2n

17,

n

1

a

2n1

,n

2(2x)n

3xn010

/

27计数问题与生成函数生成函数可以用于求解各种计数问题.计数各种类型的组合数.前面介绍了计数n元集合的允许重复的r组合数,在这些组合中可能存在某些附加的约束.这种问题与计数形如方程x1+x2+…+xn=C的解是等价的,其中C是常数,每个xi是可能具有某些约束的非负整数.11

/

27不定方程解的个数基本模型

x1+x2+…+xk

=

r

,

(r,xi为自然数)设方程的解的个数为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不定方程解的个数续基本模型

x1+x2+…+xk

=

r

,

(r,xi为自然数)设方程的解的个数为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不定方程解的个数续扩展模型(带限制条件)ni21

k

,

ylk

1

ynk

)xi

NG(

y)

(

yl1

yl1

1

yn1

)

(

yl2

yl2

1

yn2

)

(

ylk扩展模型(带系数)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的解的个数,其中ei是非负整数,满足2≤e1≤5,

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

(y3+y4+y5+y6)(y4+y5+y6+y7)的展开式中y17的系数.计算可得在这个乘积中的x17的系数是3.

因此,上面的不定方程有3个解.(注意,计算这个系数与枚举方程的具有给定约束的所有解几乎要做同样多的工作.但是这种方法常常可以用于求解各种各样的具有特殊规则的计数问题.此外,可以用计算机代数系统做这种计算.)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的系数7例例

把价值1

,

2价值k币 是有序的和无序+…)(1+x5+x10+…)5)2

+…中xk的系数,恰好n个代币产生投币6 的情况:无序

5种方法有序

15种方法解无序:(1+x+x2+…)(1+中xk

的系数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}的全排列数P(2,2)=2的某种物品3个代币:{2,2,2}的全排列数14个代币:{1,1,2,2}的全排列数4!/(2!2!)=65个代币:{1,1,1,1,2}的全排列数5!/4!=56个代币:{1,1,1,1,1,1}的全排列数1合计15种方法17

/

27使用生成函数求解多重集的r组合多重集S={n1a1,n2a2,…,nkak}的r组合数是不定方程

x1+x2+…+xk

=r,xi≤ni

(i=1,2,…,k)

的非负整数解的个数生成函数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的系数为C(r+k–1,r)18

/

27使用生成函数求解递推关系解+例

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练习计数堆栈的输出计数1,2,…n放入堆栈后的不同的输出个数.解在1进栈到出栈之间作为一个子问题,1出栈后作为一个子问题.过程如下:1进栈;处理k个数(2,…,k+1)的进栈问题;1出栈;处理k+2,…,n的进栈问题.T

(k)T

(n

1

k),

n

2T

(n)

n1k

021

/

27计数堆栈的输出递推方程求解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指数生成函数定义设{an}为序列,称n为{a}的指数生成函数.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排列的指数生成函数每一个解对应S的一个

r

组合该r

组合产生的

r排列(全排列)数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组成的五位数中,要求1出现不超过2次,但不能不出现,2出现不超过1次,3出现可达3次,4出现偶数次.求这样的五位数个数.例红,白,兰涂色1×n的方格,要求偶数个为白色,问其方案数?

!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}的生成函数,

其中

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