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

第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