复旦大学：《离散数学——组合数学》电子讲义_第七章 生成函数与递推（吴永辉）

第7章生成函数与递推关系 ◆7.1幂级数型生成函数 多重集的组合) ◆7.2指数型生成函数 ◆(多重集的排列) ◆7.3递推关系

第7章 生成函数与递推关系 7.1 幂级数型生成函数 （多重集的组合） 7.2 指数型生成函数 （多重集的排列） 7.3 递推关系

引言 ◆1.生成函数(母函数) ◆生成函数(称为母函数)是组合数学中的 个重要内容,可用来求解组合计数问题

引言 1. 生成函数(母函数) 生成函数(称为母函数)是组合数学中的一 个重要内容，可用来求解组合计数问题

◆1)例 ◆(1+aAx(+a2x)…+anx 1+(a,+a2+……+ax+(a1a2+a1a3+……+an t aa ◆x的系数为1+a2+……+am 体包含从(a112…1中取一个组合的会体 ◆x2的系数为a2+a1a2++ 体包含从a1a21an1中取两个组含的全体 ◆x3的系数为a1a2a3+a1a4+……+an2 a,a. 包含从a12…,an1中取三个组合的全体 ◆x"的系数为a1a2 体包含从12…a1中取个组合的会体

1)例: (1+a1x)(1+a2x)……(1+anx) =1+(a1+a2+……+an)x+(a1a2+a1a3+……+an- 1an)x2+……+ a1a2……anxn x的系数为a1+a2+……+an; /* 包含从{ a1, a2, ……, an }中取一个组合的全体 */ x2的系数为a1a2+a1a3+……+an-1an; /*包含从{ a1, a2, ……, an }中取两个组合的全体 */ x3的系数为a1a2a3+a1a2a4+……+an-2an-1an; /*包含从{ a1, a2, ……, an }中取三个组合的全体 */ ………… xn的系数为a1a2……an; /*包含从{ a1, a2, ……, an }中取n个组合的全体 */

◆若令a1=a2 an=1,则(1+x)=1+Cmn, 1)x+C(m,2)x2+…C(n,m ◆(1+x)=∑C(n,k)x2 ◆C(m,b:从{a,a2 an/中取k个的组 合数

若令 a 1=a 2=……=a n=1, 则(1+x) n=1+ C(n, 1)x+C(n, 2)x 2+……+C(n, n)x n (1+x) n = C(n, k) ： 从{ a 1, a 2, ……, a n }中取 k个的组 合数。 0 (, ) n k k Cnkx  

◆2)例: (+xm(+xn=(+x/m ◆左式=(C(mD)+Cm,Dx+.+Cmm)Cm 0)+Cm,1)x+…C(mn,m)x7 ◆右式=C(m+n,0)+Cm+n,1)x++Cm+n m+n)mtn ◆展开左式,得: C(m,0)xC(n, 0+/C(m, I)xC(n, 0+ C(m, O)xC(n Dx+/C(m, 2)xC(n, 0+C(m, dxC(n, 1+C(m O)XC(n, 2)1x2+..+C(m, m)XC(n, n)xm

2)例： (1+x) m(1+x) n=(1+x)m+n 左式=[C(m, 0)+C(m, 1)x+……+C(m, m)x m] [C(n, 0)+C(n, 1)x+……+C(n, n)x n] 右式= [C(m+n, 0)+C(m+n, 1)x+……+ C(m+n, m+n)xm+n] 展开左式，得： C(m, 0) C(n, 0)+[C(m, 1) C(n, 0)+ C(m, 0) C(n, 1)]x+ [C(m, 2) C(n, 0)+ C(m, 1) C(n, 1)+C(m, 0) C(n, 2)]x 2+……+C(m, m) C(n, n)xm+n

◆比较对应项的系数,得: (m+n, 1=C(m, IxC(n,0+C(m, OxC(n, (m+n, 2)=C(m, 2)xC(n, 0)+C(m, 1)XC(n, 1+ C(m, OXC(n, 2) 一般有: oC(m+n, r)=C(m, 0)C(n,r)+(m, I)C(n, r- 1)+…+C(m,r)Cmn,O ◆/ Vandermonde恒等式

比较对应项的系数，得： C(m+n, 1)=C(m, 1) C(n, 0)+ C(m, 0) C(n, 1) C(m+n, 2)= C(m, 2) C(n, 0)+ C(m, 1) C(n, 1)+ C(m, 0) C(n, 2) …………… 一般有： C(m+n, r)=C(m, 0)C(n, r)+C(m, 1)C(n, r- 1)+……+C(m, r)C(n, 0) /*Vandermonde恒等式*/

◆2.生成函数(母函数)的定义 对于序列 do,ai,a…,定义 a0+ax+ax2+….序列aoa,a2…生成 函数(母函数)。 ◆例如:(1+x是C(mn,O),C(m,1,Cm, 2,,C1m,m)的生成函数(母函数)

2. 生成函数 (母函数 )的定义 对于序列 a 0, a 1, a 2, ……，定义 a 0 + a 1x+a 2x 2+……为序列 a 0, a 1, a 2, …… 的生成 函数 (母函数 ) 。 例如： (1+x) n 是C(n, 0), C(n, 1), C(n, 2), ……, C(n, n) 的生成函数 (母函数 )

◆3.生成函数(母函数)的实例 有红球两只,白球、黄球各一只, 有多少种不同的组合方案?设;,w,y分别 代表红球,白球和黄球

3. 生成函数 (母函数 )的实例 有红球两只，白球、黄球各一只， 有多少种不同的组合方案？设r, w, y分别 代表红球，白球和黄球

◆解题思想: 红球不取(0=1),取1只(r=),取2只(r2); 中黄球不取(y2=1),取1只(y=y) 白球不取(w0=1),取1只(1l=) ◆根据乘法原理: 1+r+n2)(1+)(1+y =1+(r++y)+(r2+ny+n+y)+(y+r+ny) ◆歌一个球的组合数为3:r,,y ◆取两个球的组合数为4;p2,my,m, ◆取三个球的组合数为:r3y,F,my ◆取四个球的组合数为1:r2

解题思想： 红球不取（r0=1），取1只（r1=r），取2只（r2）； 黄球不取（y0=1），取1只（y1=y）， 白球不取（w0=1），取1只（w1=w）， 根据乘法原理： (1+r+r2)(1+w)(1+y) =1+(r+w+y)+(r2+ry+rw+yw)+(r2y+r2w+rwy) +r2yw 取一个球的组合数为3： r，w，y 取两个球的组合数为4： r2，ry，rw，yw 取三个球的组合数为3： r2y，r2w，rwy 取四个球的组合数为1： r2yw

许多组合学计数间题依赖于一个整数参数n。 这个参数n常常表示问题中某个基本集或多重 集的大小、组合的大小、排列中的位置等。因 此一个计数问题常常不是一个孤立的问题而是 系列的单个问题。 ◆例:令h表示{1,2,…,n的排列数。h2=n 于是得到数列 hh. h hn…。对于这个数 列,一般项hn=n!,通过选择n为一个特定的整 数可以得到这个问题的一个实例。如:h5=5

许多组合学计数问题依赖于一个整数参数 n 。 这个参数 n常常表示问题中某个基本集或多重 集的大小、组合的大小、排列中的位置等。因 此一个计数问题常常不是一个孤立的问题而是 一系列的单个问题。 例：令 h n表示{1, 2, …, n}的排列数。 h n=n! ， 于是得到数列 h 0, h 1, h 2, …, h n, …。对于这个数 列，一般项 h n=n!，通过选择 n为一个特定的整 数可以得到这个问题的一个实例。如： h 5=5!