第2章母函数与递推关系

第2章

母函数与递推关系

2」母函数的引入

■母函数是求解计数问题的一个强有力的工具。

■其中心思想是：将一个有限或无限序列

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

与一个函数项级数

00

(7(x)=sau(x)

n=0

联系起来，使得我们可以通过用解析的方法研究

G(x)来得到序列叫a，……的一些性质。

■最常用的函数项级数：

n

00,8X

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

〃=o""=on[

2012-9-132

2」母函数的引入

■定义2.1对于序列〃0,,称函数

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

为序列〃。4,…4,…的母函数。

■例序列C(〃,0),C(",")的母函数为

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

■例序列1,1，…，1,…的母函数为

I〃1

1+XH-•••+X+・■■=--------

1-X

2012-9-133

.■2」母函数的引入

■若我们已知某个序列的母函数，通常可通过对母

函数的操作得到该序列的一些重要性质。

■例对等式

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

两边求导得

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」母函数的引入

■在等式

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

两边同乘以X,然后再对等式的两边求导得

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」母函数的引入

■通常序列%,叫,…，〃.，…与某个问题序列p。,弋，…，々，…

的计数问题相对应，若已知序列的母函数，则可

确定该序列，从而可以解决相应的计数问题。

■例2.2有红球两只，白、黄球各一只，试求有多

少种不同的组合方案？

解所求组合方案的母函数为

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」母函数的引入

■如果只需要求不同的组合方案数，那么可考虑下

列母函数

2

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

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

■所求组合方案数为：l+3+4+3+l=12o

2012-9-137

.■2」母函数的引入

■例2.3某单位有8位男同志，5位女同志。现要组

织一个由偶数个男同志和数目不少于两个的女同

志组成的小组，试求有多少种组成方式？

解所求组成方式数序列的母函数为

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」母函数的引入

所求的组成方式数为

10+10+285+281+840+728

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

二3328

2012-9-139

q2.2母函数的性质

・几个常见的母函数：

■(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母函数的性质

■(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母函数的性质

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母函数的性质

例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母函数的性质

■得

"+5—24)

a=0,当人<24时，〃=,*>24

kk*-24)

2012-9-1314

.2・1母函数的引入

-定理1.2在n个不同的元素中取r个进行组合,

若允许重复，则组合数为C(〃+r-l,r)o

■证所求组合数的母函数为

2rn

(1+x+x+,,,+X+•,,)

n

n(n+r-

(1、r

(1-x)zX

x

U-Jr=0J

2012-9-1315

、2.2母函数的性质

-设{X.},{7为两个序列，其相应的母函数为A(x),

B(x)o

性质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母函数的性质

■性质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母函数的性质

z（X）

■性质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母函数的性质

00

00

■性质4若X叽收敛，%=Z〃，则

Ii=k

A(l)-xA(x)

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

1-X

2012-9-1319

2・2母函数的性质

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母函数的性质

■性质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母函数的性质

a

k1X

性质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母函数的性质

■性质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母函数的性质

■例计算下列和式

…(n_1>

〃=ikn7

解令

(n-n(n-1>ST)

c=

a-kb-kk

kl一「l一，I—

因为〃A=Aj，由性质5知B(x)=xCo

又叽=AJ，由性质5知A(x)=xBr(x)o

2012-9-1324

2・2母函数的性质

n-1

c(X)=%+。产+…+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母函数的性质

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

习题

■1.9试证《的正除数的数目是奇数。

证当廿1时，结论显然正确。

当〃>1时，设n的因子分解为〃=p：

2a,2a,

n=PlPl…Pk

所以N的正除数的数目是

々。，+（奇数

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

2012-9-1327

0习题

-L16n个完全一样的球，放到r个有标志的盒子

(n^r)中，无一空盒，试问有多少种方案？

-解先将r个分别放入r个盒子，然后再将剩余的n-

r个球任意地放到|•个盒子中，所求方案数为

(rn-r-(n-(n-

2012-9-1328

0习题

-解2所求组合方案的母函数为

/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

■习题

■L276位男宾，5位女宾围一圆桌而坐，

(a)女宾不相邻有多少种方案？

(b)所有女宾在一起有多少种方案？

(c)一女宾A和两位男宾相邻又有多少种方案？

解(a)先让6位男宾围圆桌坐下，有5!种方案,

再将5位女宾插入到男宾之间，有种

65432=6!

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

2012-9-1330

♦习题

■(b)将5位女宾视为一人，与6位男宾围圆桌坐下,

有6!种方案，考虑到女宾之间的次序，共有6!5!

种方案。

■(c)从6位男宾中任取两人，其方案数为C(6,2),

对于任何取定的两位男宾，将A插入到这两位男

宾之间，有2种方案，将这两位男宾与A视为一人,

与其他人围圆桌坐下，有8!种方案，所以共有

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

2012-9-1331

习题2

■2.12.42.62.48

2012-9-1332

2.3整数的拆分

■所谓整数的拆分是把一个正整数n表示成若干个

正整数的和，而这些正整数的次序是无关紧要的。

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

1+1+1+1+1是整数5的7个不同的拆分。

在整数的拆分表示〃=%+勺+…中，常使

nv>n2>..>nk

不同拆分的总数称为拆分数，通常用P(〃)表示n

的拆分数。

2012-9-1333

2.3整数的拆分

■例求(1+1+，芦中项1°的系数。

解项X20有以下三种生成方式：

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

②=.有c(ioo,1)C(99,3)种选取

方法。

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

所以项x20的系数为：

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

2012-9-1334

2.3整数的拆分

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

问能称出哪几种重量？有几种可能的方案？

解其母函数为

234

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

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

A78910

+2x+x+x+x

知能称出1到10克的重量，系数为方案数。

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

2012-9-1335

j2.3整数的拆分

■例2.11求用1角、2角、3角的邮票可贴出不同数

值邮资的方案数的母函数。

解因邮票允许重复，故其母函数为

(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的系数为4知，用1角、2角、3角的邮票贴出

数值4的方案数为4。

2012-9-1336

2.3整数的拆分

■例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整数的拆分

■例2.13整数n拆分成1,2,3,…,m的和,并允许重

复，求其母函数。若m至少出现一次，其母函数

如何？

解其母函数为

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整数的拆分

J----—

■若m至少出现一次，其母函数为

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整数的拆分

■「列2.15设有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整数的拆分

■定理2.1正整数n拆分成不同整数之和的拆分数等

于拆分成奇整数之和的拆分数。

证设〃〃表示n拆分成不同整数之和的拆分数，则

序列｛%｝的母函数为

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整数的拆分

—---

■定理2.2n拆分成其重复数不超过2的数的和，其

拆分数等于它拆分成不被3除尽的数的和的拆分

数。

证｛aj的母函数为

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整数的拆分

定理2.3n拆分成其重复数不超过k的数的和，

其拆分数等于它拆分成不被k+1除尽的数的和的

拆分数。

2012-9-1343

2.4Ferrers图象

■Ferrers图象：一^从上而下的n层格子，j为第i

层的格子数。当n.>ni+i(i=1,2,•••,n-1)时，即上

层的格子数不少于下层的格子数时，称之为

Ferrers图象。

■整数的一个拆分可以用一个Ferrers图象来表示,

图象中的每一行对应于拆分的一部分。

■例整数14的拆分6+3+3+2可以用下列Ferrers图

象来表示

2012-9-1344

,2.4Ferrers图象

■Ferrers图象的性质：

■每一层至少有一个格子；

■第一行与第一列互换，第二行与第二列互换，…，

所得到的图象仍然是Ferrers图象，这两个Ferrers

图象称为是一对共聊的Ferrers图象。

2012-9-1345

2.4Ferrers图象

■利用Ferrers图象可得到关于整数拆分的一些性质。

(1)整数n拆分成最大数为k的拆分数和数n拆分成k

个数的和的拆分数相等。

(2)整数n拆分成最多不超过k个数的和的拆分数和n

拆分成最大数不超过k的拆分数相等。

2012-9-1346

2.4Ferrers图象

■由(2)知，拆分成最多不超过m个数的和的拆分数

的母函数为

1

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

■正好拆分成m个数的和的拆分数的母函数为

11

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

2012-9-1347

2.4Ferrers图象

■(3)整数n拆分成互不相同的若干奇数的和的拆分数,

和n拆分成有自共聊的Ferrers图象的拆分数相等。

设

构造十d图象；+般A-彳物第一列都是,

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

k列都是格，这样所得的Ferrers图象是自共

聊的。反龙;亦然。

2012-9-1348

2.4Ferrers图象

■例17=9+5+3所对应的Ferrers图象为

瞪

2012-9-1349

2.6指数型母函数

回题：设有n个元素，其中式素%重复了%次，

元素〃2重复了%次，…，元素〃A重复了巴次，

%+%+.•.+%=〃,从中取r个排列，求不同的

排列数。

2012-9-1350

2.6指数型母函数

■XE理设S={%〃[,〃2〃2,…，〃A"A}为一多重集，其

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

排列।数为2A

■证排列的个数为

n•••

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

2012-9-1351

2.6指数型母函数

■例2.168个元素中勺重复了3次，心重复了2次，

%重复了3次，从中取r个，设其组合数为。一则

。。，*，。2，，一，。8的母函数为

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的系数为10知，从这8个元素中取4个组合，

其组合数为10。这10个组合是如何构成的呢？考虑

2012-9-1352

2.6指数型母函数

23223

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

=…++…)+…

其中项X产；表示1个〃「3个心。而由1个名,3

«3个所组成排列的个数为

4

4!4!x

---=>---•—

1!3!1!3!4!

2012-9-1353

2.6指数型母函数

■定义对于序列称函数〃。，〃1,n

n

xX

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

0011!n!

为序列的指数型母函数。

■例2.17序列1,1,1,…，1,…的指数型母函数为

2

XX

1+——++…=e

1!2!

2012-9-1354

2.6指数型母函数

■例2.18序列0!,1!,2!,…，k!,…的指数型母函数

为

2

xx1

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

1!2!1-x

2012-9-1355

2.6指数型母函数

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

3

数型母函数为(l-2x)2\

2012-9-1356

2.6指数型母函数

(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指数型母函数

■7E理设S=｛%%,〃2方2,•,，”A〃A｝为一多重集，其

中％+%+…+nk=n?并设a=0,1,2,...)为S

的由列：则｛J｝的指数型母函数为：

G(x)=

/n1\/n2\Znk

XXXXXX

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

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

2012-9-1358

2.6指数型母函数

■例2.22由a,b,c,d这4个符号取5个进行排列，要

求〃出现的次数不超过2次，但不能不出现；b出

现的次数不超过1次；c出现的次数不超过3次，可

以不出现；d出现的次数为偶数。求满足上述条件

排列的个数。

解设满足上述条件的r排列的个数为p,个，序列

PI，P2,…，的指数型母函数为

2012-9-1359

2.6指数型母函数

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!

■故所求排列的个数为215。

2012-9-1360

2.6指数型母函数

■例2.23求1,3,5,7,9这5个数字组成的n位数的个

数，要求其中3,7出现的次数为偶数，其它数字

出现的次数不加限制。

解设满足条件的r位数的个数为勺，则｛〃，｝对应的

指数型母函数为

23

/X2X4'XX2X3、

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

I2!4!I1!2!3!

2012-9-1361

2.6指数型母函数

(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

习题

■2.112.122.50

2012-9-1363

2.6指数型母函数

■例2.24设为7个有区别的球，将它们放进4个有标

标志的盒子，要求1,2两盒必须含偶数个球，第3

盒含奇数个球，问有多少种不同的分配方案？

解

31242141234

设将r个有区别的球放进4个有标志的盒子的方案数

为W,那么序列｛〃，｝的指数型母函数为

2012-9-1364

2.6指数型母函数

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

所求方案数为。74+2=2080

8

2012-9-1365

2.6指数型母函数

■例2.25r个有标志的球，放进n个不同的盒子，

要求无一空盒，问有多少种不同的分配方案？

解这相当于n个有标志的对象取r个作允许重复的

排列，且每个对象至少出现一次。

设排列数为。一则序列｛〃,｝的指数型母函数为

e/n

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

I2!3!

2012-9-1366

2.6指数型母函数

nA

-El

k=0IkJ

■故

a,=A)

k=。l4J

2012-9-1367

2.7递推关系举例

■例2.26Hanoi塔问题。

HABc

2012-9-1368

2.7递推关系举例

■算法的分析：设的为将n个圆盘从塔座A移动到

塔座B上所需要的移动次数，则有

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递推关系举例

■解法2：用母函数求解

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递推关系举例

■例2.28求n位十进制数中出现偶数个5的数的个数。

解设二n位十进制数中出现偶数个5的数的个