第三章 生 成 函 数课件.ppt

第三章 生 成 函 数,3.1 Fibonacci数列的生成函数 3.2 生成函数的一般性讨论 3.3 组合的生成函数 3.4 排列的生成函数 3.5 Catalan数列与Stirling数列的生成函数 3.6 分配问题 3.7 整数n分为m个类的(无序)拆分数Pmn 3.8 n的拆分数Pn的生成函数 3.9 整数n分为以h为最小类的拆分数 3.10 有序拆分,3.1 Fibonacci数列的生成函数,从 出发，推证二项式系数的若干等式，这给问题的讨论带来了许多方便。将数列 与函数 联系起来的做法，称做“生成函数（generating function）方法”。 由于将(1+x)n展开即可得到所有的 , 因此， 常称 为（有限或无限）数列ak(k=1, 2, )的生成函数或母函数。,意大利数学家Fibonacci在13世纪初提出过如下一个有趣问题： 年前养了一对小兔（雌雄各一），这对兔子中的母兔从2月份开始每月都产下一对雌雄各一的小兔。每对新生小兔间隔一月后也开始每个月都产下一对新的小兔（雌雄各一）。如是而下， 假定兔子都不死亡，问一年后共有多少对兔子？ 假定年前为0月份， 年后为13月， 不难推算各月兔子对数为 ： 月份： 0， 1， 2， 3， 4， 5， 6， 7， 8， 9， 10， 11， 12， 13， 兔子对数： 1， 1， 2， 3， 5， 8， 13， 21， 34， 55， 89， 144， 233， 377， ,著名的Fibonacci数列由此而得名。这一数列的增长速度是很快的。其中，第二年年底兔子有50 000对，第三年年底兔子有15 000 000对，第55项就超过了1万亿对。若设Fn为第n个月所有的兔子对数，则由各月兔子数不难证得如下递推式成立:,(3.1.1),下面求Fibonacci数列的生成函数F(x)：,由此得,(3.1.2),此即Fibonacci数列的生成函数。因1-x-x2的二根为,于是,因此,（3.1.3）,(3.1.4),由此表示式可以推出Fibonacci数列的组合学意义如下：,命题 1 Fn等于集合Zn-1=1, 2, , n-1中不含相继整数的子集的个数。例如，Z3=1, 2, 3的这种子集有 ，1 ，2，3， 1，3, 共F4=5个。 证明 令f(n, k)表示Zn=1, 2, , n中不含相继整数的k元子集的个数。设i1,i2,ik为此种子集，其中i1 i2 ik ，由不相继性知is-is-12，于是若记js=is-s，则必有js-js-1，反之由js js-11也可推出is-is-1 2。易证全体i1, i2, , ik与j1, j2, , jk 之间构成一双射函数。 注意到,j1=i1-10jk=ik-kn-k,可见, j1, j2, , jk为集合0, 1, , n-k的一个k元子集，这种子集的个数为C(n-k+1, k)故f(n, k)=C(n-k+1, k)，由此得,表示Zn中不含相继整数的子集数。亦即,表示集合Zn-1中不含相继整数的子集的个数。,命题 2 f*(n, k)表示不含圈(1, 2, , n, 1)中相继整数的k元子集的个数，则不含圈(1, 2, , n, 1)中相继整数的所有子集数为,其中Fn*有时也称为校正的Fibonacci数列。,证明 将满足条件的k元子集分成两类，第一类不包含n，第二类包含n。显见第一类k元子集在(1, 2, , n-1)中选取，计有f(n-1, k)种取法；第二类k元子集必不包含1与n-1, 故除去n外，余下k-1个元必须在2, 3, , n-2中选取，其取法计有f(n-3, k-1)种。 因此,从而,(1) Fn+m=FmFn+Fm-1Fn-1。证明,(3.1.5),（3.1.6）,直接由递推关系式（3.1.1）不难推得,(3.1.7),(3.1.8), 下面利用（3.1.1）式给出求Fibonacci数列的算法： 1 输入n； 2 F0 1; F1 1； 3 对k=0, n/2 打印F0, F1； F0 F0+F1; F1F1+F0;4 结束。, 求Fibonacci数列亦可采用递归算法， 主要语句如下： if n=0 or n=1 then F(n)=1 else F(n)=F(n-1)+F(n-2),3.2 生成函数的一般性讨论,定义 1 设gk(x)(k=0, 1, 2, )线性无关，则称,为ak(k=0, 1, 2, )的生成函数。,(3.2.1)式称为关于未定元x的形式幂级数，它是从代数学观点引入的。对于实数R上的数列ak及R上的未定元x，称表达式(3.2.1)为R上的形式幂级数。一般情况下，形式幂级数中的x只是一个抽象符号，并不需要对x赋予具体数值，从而避开了讨论级数收敛性的问题。,(3.2.1),R上关于未定元x的形式幂级数的全体记为R(x)。在集合R(x)中适当定义加法（+）和乘法()， 则(R(x), +, )构成环。该环中的元素即为形式幂级数。 设 若对任意k0，有ak=bk，则称A(x)与B(x)相等，记为,A(x)=B(x),为与A(x)的数乘积。,设A(x)、B(x)定义如上，则可定义二幂级数的加法运算为,并可根据gk(x)的不同形式定义A(x)与B(x)的乘积(如下面的定义3)。 在环(R(x), +, )上，还可定义形式幂级数的形式导数。对 ， 规定,称DA(x)为A(x)的形式导数。,A(x)的n次形式导数可以递归地定义为D0A(x)=A(x)DnA(x)=D(Dn-1A(x), n1,可证，形式幂级数的形式导数满足如下规则： （1） D(A(x)+B(x)=DA(x)+DB(x)； （2） D(A(x)B(x)=A(x)DB(x)+B(x)DA(x); （3） DAn(x)=nAn-1(x)DA(x)。,生成函数有如下几种：(1) 取gk(x)=xk, 则有,此式常称为寻常或普通（Ordinary）型生成函数。,(2) 取gk(x)=xk/k!, 则有,此式常称为指数（Exponential）型生成函数。,(3) 取gk(x)=1/kx, 则有,此式即为Dirichlet生成函数。,(4) 取gk(x)=xk, 则有,此式常称为下阶乘生成函数。,定义 2 设A(x), B(x)分别为ak与bk的生成函数，则A(x)+B(x)=C(x)为cn的生成函数，其中:,ck=ak+bk,定义 3 设A(x), B(x)分别为ak与bk的生成函数，则A(x)B(x)=C(x)为cn的生成函数，其中： (1) 在寻常生成函数 的情形下，有,(2) 在指数型生成函数 的情形下， 有,(3) 在Dirichlet生成函数 的情形下， 有,(1),证明 令B(x)=b0+b1x+b2x2+bm-1xm-1+bmxm+bm+1xm+1+， 据前提知,(2),证明,据假设知,例 2 设,(3),证明 由假设,等式左端相加, 显见为。 等式右端相加, 得,故,类似可得,证明 因 收敛，故bk存在。下面考察B(x)中xk的系数(k=0, 1, 2, )。,从而,(5),例 4,(6),(7),例 5 设A(x)=1+x+x2+=1/(1-x), B(x)=x+2x2+3x3+=x/(1-x)2， 且,易知,3.3 组合的生成函数,与组合问题有关的计数常使用寻常生成函数。 命题 设多重集S=r1e1, r2e2, , rmem, 且r1 + r2 + rm=n, 则S的k可重组合数ck对应序列ck的生成函数为,其中，k可重组合数ck为G(x)展开式中xk的系数。,证明 令G(x)中各的项分别对应诸元素的某种可能取法。 例如, 对i=t, xr表示元素et选取了r次。依次类推。 显见G(x)展开式中的项xk具有一般形式,其中,k1+k2+km=k, 0kiri, i=1, 2, , m,对此方程的一非负整数解(k1,k2, , km)（在前提0kiri, i=1, 2, , m下），乘积就对应了诸元素e1, e2, , em的一种可重取法。合并同类项后，xk的系数就表示了从多重集S中取出k个元素的所有可能的可重组合数ck。,推论 1 设S=e1, e2, , em，则S的k可重组合数ck对应序列ck的生成函数为G(x)=(1+x)m其组合数ck为G(x)展开式中xk的系数,推论 2 设S=e1, e2, , em，则S的k（无限）可重组合数ck对应序列ck的生成函数为,其组合数ck为G(x)展开式中xk的系数C(m+k-1, k)。 推论2无0kiri, i=1, 2, , m限制，由2.6节中例10即知ck=C(m+k-1, k),推论 3 设S=e1, e2, , em，则S的每个元素至少取一次的k（无限）可重组合数ck（km）对应序列ck的生成函数为,其组合数ck为G(x)展开式中xk的系数C(k-1, m-1)。这是由于,推论 4 设S=e1, e2, , em，且S的每个元素出现非负偶数次，则S的k（无限）可重组合数ck对应序列ck的生成函数为,其组合数ck为G(x)展开式中xk的系数，即,推论 5 设S=e1, e2, , em，则S的每个元素出现奇数次的k（无限）可重组合数ck对应序列ck的生成函数为,其组合数ck为G(x)展开式中xk的系数，即,推论 6 设S=e1, e2, , em，若限定元素ei出现的次数集合为Pi(1in)，则从S中取出k个元素的组合数ck对应序列ck的生成函数为,推论 7 设多重集S=r1e1, r2e2, , rmem，且r1+r2+rm=n，则S中的每个元素ei至少出现ki(i=1, 2, , m)次的r可重组合数cr对应序列cr的生成函数为,其组合数cr为G(x)展开式中xr的系数， r=k, k+1, , n; k=k1+k2+km。,例 1 求不定方程k1+k2+k3+k4=20的解组数。其中，限制k1可取0，2，4；k2可取1，3，5；k3可取6，7；k4可取8，9。 解 设不定方程 的解组数目为ck，本例中m=4, k=20。注意到对ki(i=1, 2, 3, 4)的限制，序列ck对应的生成函数为G(x)=(1+x2+x4)(x+x3+x5)(x6+x7)(x8+x9)由G(x)展开式中x20的系数知题给不定方程解组数目为c20=6。,注意，有时会因对ki的限制使ck取值为0。例如，对S=a, b, c，若限制a可重复1，3，5次；限制b可重复2，4，6次；限制c必须出现6次，则由G(x)=(x+x3+x5)(x2+x4+x6)x6虽可求出c9=c17=1, c11=c15=2，c13=3, 但对小于9及偶数的k, ck的取值全为0。,例 2 求S=3a, 4b, 5c的10组合数。 解 设S的k组合数为ck，则ck对应的生成函数为,展开式中x10的系数,即S的10组合数为6。,例 3 设有5个红球和8个黄球，要求每次取出不少于2个红球和偶数个黄球，求所有的组合方式数。 解 组合方式数对应序列的生成函数为,因此，总的组合方式数为1+1+28+1+1=20。,若考虑同色球各不相同或加有标记，这时可分别设红球与黄球取法所成序列的生成函数为A(x)与B(x)。 易知,从而,C(x)展开式中xk的系数即为每次取出k个球的组合方式数，总的组合方式数目为所有系数之和。,例 4 设有红球2个， 黑、 白球各1个， 问 （1） 共有多少不同的选取方法？试加以枚举。 （2） 若每次从中任取3个， 有多少种不同取法？ 解 （1）设用r，b，w分别代表红、黑、白三种球，两个红球的取法与r0, r1, r2对应，即红球的可能取法与1+r+r2中r的各次幂一一对应，亦即r0=1表示不取红球，r表示取1个红球，r2表示取2个红球。对其它球， 依此类推法， 则不同选取方法数所成序列对应的寻常生成函数为,分析上式， 不难发现 1： 一个球都不取， 仅有一种方案； r+b+w： 取1个球的方案有3种， 分别为红， 黑， 白； r2+rb+rw+bw：取2个球的方案有4种，分别为红红，红黑，红白， 黑白； r2b+r2w+rbw：取3个球的方案有3种，即2红1黑，2红1白，三色球各取其一； r2bw：取4个球的方案仅1种，即所有球全取。 若令r=b=w=1，即可求得所有不同的选取方案总数为G(1, 1, 1)=1+3+4+3+1=12,（2） 若只考虑每次取3个球的方案数，而不需枚举，则可令r=b=w=x。写出G(x)=(1+x+x2)(1+x)2=1+3x+4x2+3x3+x4由x3的系数知所求方案为3种。,例 5 18张参观券分发给a, b, c, d四个小组，其中各组分配票数ra, rb, rc, rd分别为1ra5, 1rb6, 2rc7, 4rd10。 求所有不同的分配方案数。 解 这实际上相当于由a, b, c, d四类共5+6+7+10=28个元素中可重复地取18个元素的组合问题。各类球取法的下界ki(i=1,2,3,4)分别为1, 1, 2, 4；上界ri分别为5, 6, 7, 10。 m=4, n=18。 由推论6知相应的生成函数为,由x18前的系数知，共有140种分配方案。,若将票数改为n=4，各组所分票下界数改为ki=0(i=1, 2, 3, 4)， 上界不变，这时,与,中x4的系数是一样的，但用G2(x)求解要比用G1(x)求解方便得多。,同理，当n=6时， 可以用,来代替G1(x)求x6的系数。,例 6 求一粒骰子连续投掷两次， 出现点数之和为10的概率。 解 设骰子各点出现的概率均等。 解法 1 投掷一次出现的点数有6种，连续投掷两次所得点数共有66=36种可能。 由枚举法， 两次投掷出现点数之和为10的方案恰有3种： (4, 6)， (5, 5)， (6, 4)， 故出现点数之和为10的概率为3/36=1/12。,解法 2 依题意，投掷骰子出现点数所成序列的生成函数为,由x10的系数为3知有3种点数之和为10的方案，故知所求概率为3/36=1/12。 初看解法二比解法一要复杂一些，但若将问题改为一粒骰子连续投掷10次，求出现点数之和为30的概率时，解法二就显得有力多了。 这时,不难算得x30前的系数为 2 930 455， 故所求概率为,3.4 排列的生成函数,当涉及到与排列有关的问题时，通常使用指数型生成函数。 由于 , 可见 或nk的生成函数为(1+x)n。 因G(x)=(1-x)-1=1+x+x2+,故其为序列1, 1, 1, 的寻常生成函数。又因 , 显见序列1, 1, 1, 的指数型生成函数为Ge(x)=ex。,命题 1 若元素e1可重复1, 2, 次，元素e2可重复1, 2, 次，元素em可重复1, 2, 次，则m元集的这种k可重排列数Pk对应序列Pk的生成函数为,事实上，上式右端等于,由多项式系数的组合学意义知，(k!/ i1 ! i2 ! im !)正是元素e1出现i1次，元素e2出现i2次，元素em出现im次的k可重排列数。故按所有可能的i1+i2+ im =k求和，即得总的k排列数Pk。,推论 1 设S=e1, e2, , em，若元素ei(i=1, 2, , m)重复出现的次数构成集合i，则集S中元素的这种k可重排列数Pk对应序列Pk的生成函数为,k可重排列数Pk为G(x)展开式中xk/k!的系数。,推论 2 设m元多重集S=r1e1, r2e2, , rmem，且r1+ r2 + rm =n，则S的k可重排列数Pk对应序列Pk的指数型生成函数为,其中，k可重排列数Pk为Ge(x)展开式中xk/k!的系数(k=0, 1, 2, )。,例 1 3个红球，2个黄球，3个蓝球，每次从中取出4个排成一列， 求排列方案数。 解 m=3, r1=3, r2=2, r3=3, k=4, 由推论2知,故知，从所给n色球中取出4个的排列方案有70种。 类似于组合问题， 令,从中可以看出，取1个球的3种排列方案为：r, y, b，即红，黄， 蓝分别取其一; 取2个球的9种排列方案为：rr, yy, bb, ry, rb, by, yb, yr, br。,推论 3 设S=r1e1, r2e2, , rmem，则S中元素的k（无限）可重排列数Pk对应序列Pk的指数型生成函数为,其中，k排列数Pk为xk/k!的系数mk。,推论 4 特别地，若每个元素ei至少出现一次（这时有kn）， 则 Ge(x)=(ex-1)m，从中取出k个元素的可重排列数,事实上，因每个元素至少出现一次的k排列数Pk的生成函数为,故有,应用如下几个算子：差分算子： f(x)=f(x+1)-f(x)移位算子E： Ef(x)=f(x+1)恒等算子I： If(x)=f(x)上式之Pk可以简写成,定义移位算子Ea：Eaai=ai+1, Ebbi=bi+1，任一指数生成函数可写成,同样,于是,因此若,则,此即3.2节中的（3.2.8）式。 上述过程可以更简洁地写成,A(x)=eax, aiaiB(x)=ebx, bibicn=(a+b)n, aiai, bibi,后一式表示将(a+b)n按通常方式展开，再易ai为ai, 易bi为bi。,命题 2 （Bernoulli求和公式）,证明 记Ef(x)=f(x+1)为移位算子，If(x)=f(x)为恒等算子，f(x)=f(x+1)-f(x)为差分算子，不难证得=E-I。于是,由此可见,此式两边算子施于f(1)，即得所证。,Bernoulli求和公式一般用于f(x)为多项式的场合，此时f(x)的高阶差分等于零。如对f(x)=x3, 逐次计算if(x)，如下所示：,k 1 2 3 4 5 f(k) 1 8 27 64 125f(k) 7 19 37 612f(k) 12 18 243f(k) 6 64f(k) 0,于是,f(1)=1, f(1)=7, 2f(1)=12, 3f(1)=6,4f(1)=5f(1)=0,应用求和公式即得,推论 5 设S=r1e1, r2e2, , rmem，若要求元素ei至少取ki个（ ki 0），则这种排列数形成序列的生成函数为,推论 6 设S=r1e1, r2e2, , rmem，且r1+r2+rm=n，取k=n，即得全排列数为,例 2 五个数字1，1，3，3，5能组成多少4位数？解 令Pk表示组成k位数的个数，Pk的指数型生成函数为,由P4=30知能组成30个4位数。,例 3 求1， 3， 5， 7， 9五个数字组成的n位数的个数。要求其中3，7出现偶数次，1，5，9出现的次数不限。 解 设满足条件的n位数的个数为Pn，则Pn对应的指数型生成函数为,故,是n元多重集（重复次数不限）每个不同元素出现偶数次的k排列数所成序列的指数生成函数。,例 5,是n元多重集（重复次数不限）第一个元素出现0，2或5次，第二个元素出现1，2或6次，其余n-2个元素出现的次数不加限制的k排列数的指数生成函数。,例 6 确定k格棋盘的3染色方法数，其中白色染偶数格，其余两种颜色所染方格数不限。 解 令ak表示这种染色数，并定义a0为1。则ak等于三色多重集（每种颜色重复次数不限）白色出现偶数次的k排列数。 于是序列a0, a1, , ak, 的指数生成函数为,从而,由2.10节中命题3知, xn是第二类Stirling数Snk的下阶乘生成函数。又由2.10节中定义5及命题10可见,xn是第一类Stirling数skn的寻常生成函数，xn是| skn |的寻常函数。两类Stirling数是沟通xn, xn, xn这三种首项为1的多项式的桥梁。,3.5 Catalan数列与Stirling数列的生成函数,定义 1 空集或有限点集T，满足： (1) 有一特定结点r称为“根”； (2) 删除根r，则剩下的点Tr组成两棵子二叉树：Tl（左子树）及Tr(右子树)。,3.5.1 Catalan数列的生成函数 例 1 二叉树（或二元树）的计数问题。 例如， 3个结点可有5棵不同的二叉树, 如图3.5.1所示。,图 3.5.1 二叉树,一般地，设cn为n个结点的不同的二叉树的个数，则有c0=1。 在n0的情形下，二叉树有一个根结点及n-1个非根结点，设左子树Tl有k个结点，则右子树Tr有n-1-k个结点，于是不同的左子树有ck种，右子树有cn-1-k种， 从而,比较上式与3.2节中(3.2.7)式， 可见对应二叉树数目的生成函数B(x)=c0+c1x+c2x2+满足方程xB2(x)=B(x)-1, B(0)=1,解此二次方程，并应用二项式定理得,因此,例 2 设有一n+1(n2)边的凸多边形，若用连接不交对角线的方法把该多边形进行三角剖分，求所有不同的剖分方案数。 解 令hn表示将n+1(n2)边凸多边形进行三角形剖分的方案数，则当n=1时，h1=1，当n3时，任取多边形一边记作e，其两端点一端记为v1，一端记为vn+1，余点依次相邻标记如图3.5.2所示。现以v1，vn+1及任意顶点vk+1(k=1,2,n-1)构作一三角形，该三角形将凸多边形分为F1, F2两个区域。其中，F1由k+1边凸多边形围成，其三角形剖分方案数为hk，F2由n-k+1边凸多边形围成， 其三角形剖分方案数为hn-k，由乘法原理知。 易证,当n=5时， 可求得,图3.5.2 余点依次相邻标记,图 3.5.3 凸6边形的14个剖分方案,3.5.2 Stirling数列的生成函数 为醒目起见，把第一类与第二类Stirling数分别记为S1(n,k)与S2(n, k)。 （1） 序列S1(n, k)的指数型生成函数为,（2） 序列S2(n, k)的指数型生成函数为(et-1)k/k!, 且有,（3） 序列S2(n, k)的寻常生成函数为,并且还有,证明 （1）,两端同乘以tn/n!, 并对n求和有（3.5.1）式,（3.5.1）,故（3.5.1）式可改写如下：,因为 S0(t)=1，Sk(0)=0， 所以,这就证明了序列S1(n, k)的指数型生成函数为,(2) 据2.10节中命题3有,另一方面，对于任意正整数t，应用移位算子E、差分算子及恒等算子I， 有,由此即知,又由2.10节命题2的推论2知,故,这就证明了S2(n, k)的指数型生成函数为,且,(3) 对递归关系S2(n+1, k)=S2(n, k-1)+kS2(n, k)两端同乘以tn+1， 并对n求和，得,即,令,则有,故,从而,等式右端展开后，各tn-k项的一般形式为,其中，ni0(i=1, 2, , k), 且 。合并同类项后知tn-k的系数为,其中，n1, n2, ,nk 是满足上述不定方程的一切有序非负整数解组， 因此,例如，对S2(n, k)，n=5，k=3，n-k=2，n1+n2+nk=2 的所有有序非负整数解组为（2， 0， 0）, （0， 2， 0）, （0， 0， 2）； （1， 1， 0）, （1， 0， 1）, （0， 1， 1）。 故知S2(5,3)=12+22+32+1121+1131+2131 =1+4+9+2+3+6=25 Fibonacci数列，Catalan数列及Stirling数列形成组合数学中三种典型的数列，实际应用中许多组合计数结果都与它们相同或相似。,3.6 分 配 问 题,3.6.1 盒子不相同的分配问题 命题 1 有n个相同的球，m个不同的盒子，各盒的容量分别为ni(ni0,i=1,2,m)。则其分配序列的寻常生成函数为,证明 本命题与3.3节中的命题是一样的。这里可将m个盒子看成m个元素，记为e1, e2, , em，n个相同的球中分别有:,x1个球放入e1，即e1被选取x1次， x1 n1； x2个球放入e2，即e2被选取x2次，x2n2； xi个球放入ei，即ei被选取xi次，xini； xm个球放入em，即em被选取xm次，xmnm。 以上放法可记为：,且x1+x2+xm=n, 0 xini, i=1, 2, , m。 以上放法仅与ei的出现次数有关，而不考虑ei的顺序。因此， 满足命题条件的分配问题可归结为多重集S=n1e1, n2e2, , niei, , nmem的n-可重组合问题，故其生成函数与3.3节命题相同。,推论 1 若各盒容量ni=1(i=1, 2, , m)，球数nm， 则其分配序列的生成函数为(1+x)m，且分配方案数为,推论 2 若各盒的容量不加限制，则其分配序列的生成函数是(1-x)-m，其分配方案数为C(m+n-1, n)。 证明 由于各盒容量不加限制，故生成函数为,推论 3 若各盒的容量不加限制， 但不允许有空盒， 则其分配序列的生成函数为,且其分配方案数为 。,推论 4 若各盒容量限制为非负偶数, 则其分配序列的寻常生成函数是(1-x2)-m，分配数是,n为偶数,n为奇数,其生成函数为,其中n=2k为偶数。,推论 5 若各盒的容量限制为奇数，则其分配序列的寻常生成函数是x/(1-x2)m，其分配方案数是,命题 2 有n个不同的球，m个不同的盒子，各盒的容量ni(ni 0, i=1, 2, , m)。 则其分配序列的指数型生成函数为,证明 将n个不同的球放入m个不同的盒子（盒子加有编号）， 每次不同的放法可按如下方式记录。用b1, b2, , bn表示n个不同的球，用e1, e2, , em表示m个不同的盒子。,b1b2bnn个不同的球已按某种顺序排好j1j2jn各球所占盒子的编号(反映于下标)其中ji1, 2, , m(i=1, 2, , n)。对球的分配不同，排列j1j2jn也就不同；反之，不同的排列j1j2jn对应了球的不同分配。而这种排列正是m个元素的n-可重排列。其中每个元素的重复次数分别是n1, n2, , nm。从而问题归结为集合S=n1e1, n2e2, , nmem的n-可重排列。故其生成函数为,推论 1 若各盒的容量ni=1(i=1, 2, , m)，则其分配方案数为P(m, n)(nm)，其生成函数为,推论 2 若各盒容量ni0且n1+n2+nm=n，则其分配方案数为n! /(n1! n2! nm!)。其生成函数为,推论 3 若各盒容量不加限制，则其分配序列的生成函数为,显见其分配方案数为mn。,推论 4 若各盒非空（即ni0, i=1,2,m）。分配方案数为A(n,m)=m!S(n,m)。且分配序列的生成函数为(ex-1)m。,推论 5 若指定r个盒非空，其余m-r个盒的容量不加限制， 则其总的分配方案数为,证明 不妨假定前r个盒非空，其中放入k个球(rkn), 则因由n个球中任取k个的选法有 种；又k个球放入r个盒中，各盒非空，据推论4知分配方案数为A(k, r)。,把剩余的n-k个球不加限制地放到m-r个盒中，据推论3可知分配方案数为(m-r)n-k。 由乘法原理，二不同分配方案数为 A(k, r)(m-r)n-k。注意到k可取r, r+1, , n, 共n-r+1种情况，再由加法原理，即得总的分配方案数为,推论 6 若有r个以上的空盒， 则其分配方案数为,证明 空盒数sr，与非空盒数m-s取法对应罗列如下：,空 盒 数 s=r, r+1, , m-1， m非空盒数 m-s=m-r, m-(r+1), , 1, 0,若干个染有颜色的球，同色球看作一个类，同类中的球视为是相同的。若恰有1个球的颜色有k1种，恰有2个球的颜色有k2种，恰有s个球的颜色有ks种，可将所有球分类的型记为k1 1+ k2 2+ ks s或者记为 例如，14个球染有赤、 橙、 黄、 绿、 青、 蓝、 紫7种颜色， 即分为7个类， 且各种颜色相应的数量分别为2，1，3，2， 1，2，3， 则这14个球分类的型为122332。,命题 3 m个不同的盒子，分类的型为的n个球，k1+2k2+sks=n，若各盒的容量不限，则其分配方案数是,证明 对n个球按分类情况分别考虑如下： 对1k1： k1个1类中每类1个球，这相当于将k1个不同的球分配给m个不同的盒子，由命题2的推论3知其分配方案数是,对2k2：k2个2类中每类2个球，这每类中的2个相同的球分配给m个不同的盒子，由命题1的推论2知其分配方案数是 。 因共有k2个2类，类不同，球不同，故共有 种分配方案； 对sks：ks个s类中每类s个球，这每类中的s个相同的球分配给m个不同的盒子，由命题1的推论2知其分配方案数是 因共有ks个s类，类不同，球不相同，故共有 种分配方案。,以上各种情况中， 不同型的类间球均不相同，因此，不同情况间分配方案彼此无关。 故由乘法原理可知，满足命题条件的全部分配方案数为,3.6.2 盒子相同的分配问题 命题 4 n个不同的球，m个相同的盒子，各盒非空，则其分配方案数是Snm。 推论 n个不同的球， m个相同的盒子，若各盒容量无限制， 则分配方案数是,命题 5 n个相同的球，m个相同的盒子，各盒非空，则其分配序列的生成函数是,分配方案数是G(t)展开式中tn的系数。 命题5相当于将整数n拆分成m部分的无序拆分， nm。(其证明参见随后几节。),命题 6 n个不同的球，m个相同的盒子，其分配序列的生成函数为,分配方案数是G(t)展开式中tn的系数。 命题6相当于将整数n拆分成k部分的无序拆分， k=1, 2, , m。,表 3.6.1 分配问题的几种常见解决方案,3.7 整数n分为m个类的（无序）拆分数Pmn,定义 1 整数（无序）拆分是指把整数分解成若干整数的和，若各部分不允许出现0值时，则称各部分为类。 整数（无序）拆分的组合学意义相当于把n个无区别的球放入若干相同的盒子的放法（各盒子中可放入t个球, 1tn）；或者将其看作n元集X的划分（无空盒子）的型，每个型对应于适合条件：,及 a1a2a3am1,的一个m元组(1, 2, , m)。该m元组通常就称为整数n的一个拆分。整数n分成恰有m个类（或称非零部分）的拆分个数，记作Pmn。,例如：整数n 拆分方式 拆分个数 2 2, 1+1 3, 3, 2+1, 1+1+1 4, 4, 3+1, 2+2 2+1+1, 1+1+1+1,命题 1 递归关系:,证明 只证第一式。设E是将n分成不多于k个类的拆分的集合。属于E的每个拆分可看成是一个k元组（其分量用0补足k位）。在E上定义映射, (a)=a。,a=(a1, a2, , am, 0, 0, , 0)a=(a1+1, a2+1, , am+1, 1, 1, , 1),在此映射下，E被映入将n+k分成恰有k个类的拆分的集合E。因此 （1）,（2） 对aE aE 使(a)=a,可见, 为一双射函数。因此,第二个公式直接从定义可得。,推论 注意到jn时有Pjn=0, 故对kn 有,利用命题1及其推论给出的公式，可递归地推算Pmn如下：,Pmn m=1 2 3 4 5 6n=1 1 2 1 1 3 1 1 1 4 1 2 1 1 5 1 2 2 1 1 6 1 3 3 2 1 1, 求拆分三角的算法:1 定义数组P=(1：n, 1：n);2 对k=1, n, 做 P(k, 1) 1; P(k, k) 1;3 打印P（1， 1）； 打印P（2， 1）， P（2， 2）；4 对i=3, n, 做 4.1 对j=2, i-1, 做 S 0; n1 i-j; n2min(j, n1); 对t=1, n2, SS+P(n1, t); P(i, j)S; 4.2 对j=2, i，做 按行打印P(i, j)； 5结束。,命题 2 n分成k个类的拆分的个数，等于n分成以k为最大类的拆分的个数。例如，当n=6时，以3作为最大类的拆分有3个:3+1+1+1， 3+2+1， 3+3而分成3个类的拆分也有3个： 4+1+1， 3+2+1， 2+2+2,证明 考虑一个拆分，例如5+4+1+1，并构作一个相应的图（称为Ferrer图解，见图3.7.1），在图中每个类均表示成一行小方块，每行的方块数等于类本身的数目，考虑到拆分元组的分量由左向右成一递减序列，故对应的Ferrer图从上而下，各行方块数也自然呈递减数列。,图 3.7.1 5+4+1+1对应的Ferrer图,定义a*=(a*1, a*2, , a*a1)为a=(a1, a2, , ak)的共轭拆分，其中a*1是a的基数不小于i的类的个数。上例中，不小于4的类有4个，故a*1 =4; 5, 4 都是不小于2、3及4的类，故a*2 =a*3=a*4=2; 又不小于5的类只有5，即a*5=1。从而共轭于5+4+1+1的拆分是4+2+2+2+1。与共轭拆分对应的Ferrer图显见可由原拆分的Ferrer图绕对角线旋转而得。 易证由n的拆分的集合E到共轭拆分的集合E*间存在一双射函数。与此同时，也建立了n分为以k为最大类的拆分的集合与n分为k个类的拆分的集合间的双射函数。,定义 2 若n的一个拆分的Ferrer图像与它的共轭拆分的Ferrer图像完全相同， 则称该拆分是自共轭拆分。,命题3 n的自共轭拆分的个数等于n分成各类都不相等且都是奇数的拆分的个数。 证明 设, 其中 n1n2nk。显见这是一个把n分成各类都不相同且都是奇数的拆分，对应的Ferrer图像的第i行有2ni+1个方格。构造一新的Ferrer图像，使其第i行及第i列都是ni+1个方格。注意到交叉处的方格重合，故这恰用掉原Ferrer图像的第i行的2ni+1个方格。而新构造的Ferrer图像以对角线为轴线对称， 即对应的拆分是自共轭的。 反之，对任一自共轭拆分，用其Ferrer图像中第i行及第j列的全部方格（共2ni+1个）作为新构造的Ferrer图像的第i行，这新得到的图像对应的拆分又是n分成各类都不相等且都是奇数的拆分。以上讨论建立了两种拆分间的双射函数。,命题 4 n分成各类互不相同的拆分的个数， 等于n分成各类都是奇数的拆分的个数。 证明 设，其中ni为奇数，ri为ni的重复次数。注意到rt可表示为,断言,n= b020n1+b121n1+b020n2+b121n2+ +b020ni+b121ni+b020nj+b121nj+,中取掉0项（bk=0），就构成n的各类互不相等的拆分。事实上,若s=t，显见有ninj；若st（不妨设ts）, 但ni=nj2t-s， 这导致ni为偶数，与题设矛盾，故断言为真。又上述构造过程的逆也成立。 这就建立了两种拆分间的双射函数。,命题5 设Qn是n分为偶数个互不相等的类的拆分类, Qn是n分为奇数个互不相等的类的拆分数，则,证明 考虑把n分成奇数个互不相等的类的一个拆分：在该拆分的Ferrer图中，用S表示最底层方块的集合, 用E表示最右边45线上的方块集合（S和E有可能只包含同一方块）, 参见图3.7.2。 如果|S|E|，则把S中的方块移到前|S|行的最右端，得到图3.7.3所示的新拆分。,图 3.7.2 奇数个类，|S|E|,图 3.7.3 偶数个类， |S|E|,若原来就是|S|E|，则把集合E中的全部方块移到最底层， 从而得一偶数个互不相等类的新拆分（且|S|E|）。这种操作手续除以下两种例外总是可行的。 （1） S与E相交且|S|=|E|：S不能移到右方； （2） S与E相交且|S|=|E|+1：E无法移到下方。,图 3.7.4 两种例外情况,在以上两种情形下，令|E|=k，=0(图3.7.4（i）的情形）或=1（图3.7.4（ii）的情形）,除去n满足上式的情形外，其余的类不等奇拆分与类不等偶拆分间形成一双射函数。,3.8 n的拆分数Pn的生成函数,命题 1 n的拆分数Pn的生成函数是,证明 只需证,事实上，当|x|1时，有,在xn的系数中，第一项 确定n的一个拆分，即,最后，取a1=a2=1，即得上述公式。,命题 2 Pnm的生成函数是,命题 3 n分成仅由奇数类构成的拆分数的生成函数是,命题 4 n分成各类互不相等的拆分数的生成函数是,G4(x)=(1+x)(1+x2)(1+x3),命题 5 n分成互不相等的奇数类的拆分数的生成函数是,命题 6 G3(x)=G4(x)。 (3.7节命题4)证明 事实上，,命题 7 （Euler等式）,(1-x)(1-x2)(1-x3)=1+ (n)xn=1-x-x2+x5+,是(n)的生成函数，其中,证明 由3.7节命题