组合数学课件：生成函数

生成函数3.1Fibonacci数列的生成函数

3.2生成函数的一般性讨论

3.3组合的生成函数

3.4排列的生成函数

3.5Catalan数列与Stirling数列的生成函数

3.6分配问题

3.7整数n分为m个类的(无序)拆分数Pmn

3.8n的拆分数Pn的生成函数

3.9整数n分为以h为最小类的拆分数

3.10有序拆分3.1Fibonacci数列的生成函数

从 出发，推证二项式系数的若干等式，这给问题的讨论带来了许多方便。将数列 与函数 联系起来的做法，称做“生成函数（generatingfunction）方法”。由于将(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数列由此而得名。这一数列的增长速度是很快的。其中，第二年年底兔子有50000对，第三年年底兔子有15000000对，第55项就超过了1万亿对。若设Fn为第n个月所有的兔子对数，则由各月兔子数不难证得如下递推式成立:(3.1.1)下面求Fibonacci数列的生成函数F(x)：由此得(3.1.2)此即Fibonacci数列的生成函数。因1-x-x2的二根为于是因此（3.1.3）若从比较系数，可得二项式系数表示的Fn为(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-1≥2，于是若记js=is-s，则必有js-js-1，反之由js＞js-1≥1也可推出is-is-1≥2。易证全体{i1,i2,…,ik}与{j1,j2,…,jk}之间构成一双射函数。注意到j1=i1-1≥0∧jk=ik-k≤n-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)

(2)证明注意到对任一级数有成立，于是从1=F(x)(1-x-x2)=F(x)(2-x-x2)-F(x)得F(x)=F(x)(2-x-x2)-1=F(x)(2+x)(1-x)-1=F(x)(2+x)-(1-x)-1

比较两边xn之系数即得（3.1.6）式。（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;F1

F1+F0;

№4结束。·

求Fibonacci数列亦可采用递归算法，主要语句如下：

ifn=0orn=1thenF(n)=1elseF(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),+,·)构成环。该环中的元素即为形式幂级数。设 若对任意k≥0，有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)),n≥1

可证，形式幂级数的形式导数满足如下规则：（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)=［x］k,则有此式常称为下阶乘生成函数。

定义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)在寻常生成函数的情形下，有特别取若{ak}的生成函数为A(x)，

则的生成函数为(2)在指数型生成函数 的情形下，有(3)在Dirichlet生成函数 的情形下，有(1)

证明令B(x)=b0+b1x+b2x2+…+bm-1xm-1+bmxm+bm+1xm+1+…，据前提知例1

设则(2)证明

据假设知例2设

(3)证明由假设

等式左端相加,显见为 。等式右端相加,得故例3

设A(x)=1/(1-x),,则类似可得(4)收敛,且

证明因收敛，故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={r1·e1,r2·e2,…,rm·em},且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,0≤ki≤ri,i=1,2,…,m

对此方程的一非负整数解(k1,k2,…,km)（在前提0≤ki≤ri,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无0≤ki≤ri,i=1,2,…,m限制，由2.6节中例10即知ck=C(m+k-1,k)

推论3

设S={∞·e1,∞·e2,…,∞·em}，则S的每个元素至少取一次的k（无限）可重组合数ck（k≥m）对应序列{ck}的生成函数为其组合数ck为G(x)展开式中xk的系数C(k-1,m-1)。这是由于

推论4

设S={∞·e1,∞·e2,…,∞·em}，且S的每个元素出现非负偶数次，则S的k（无限）可重组合数ck对应序列{ck}的生成函数为其组合数ck为G(x)展开式中xk的系数，即当k为偶数时当k为奇数时

推论5

设S={∞·e1,∞·e2,…,∞·em}，则S的每个元素出现奇数次的k（无限）可重组合数ck对应序列{ck}的生成函数为其组合数ck为G(x)展开式中xk的系数，即若2|(k-m)若k-m为奇数

推论6

设S={∞·e1,∞·e2,…,∞·em}，若限定元素ei出现的次数集合为Pi(1≤i≤n)，则从S中取出k个元素的组合数ck对应序列{ck}的生成函数为

推论7

设多重集S={r1·e1,r2·e2,…,rm·em}，且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={3·a,4·b,5·c}的10组合数。解设S的k组合数为ck，则{ck}对应的生成函数为展开式中x10的系数即S的10组合数为6。

例3

设有5个红球和8个黄球，要求每次取出不少于2个红球和偶数个黄球，求所有的组合方式数。

解组合方式数对应序列的生成函数为因此，总的组合方式数为1+1+2×8+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种。

例518张参观券分发给a,b,c,d四个小组，其中各组分配票数ra,rb,rc,rd分别为1≤ra≤5,1≤rb≤6,2≤rc≤7,4≤rd≤10。求所有不同的分配方案数。

解这实际上相当于由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种，连续投掷两次所得点数共有6×6=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前的系数为2930455，故所求概率为3.4排列的生成函数

当涉及到与排列有关的问题时，通常使用指数型生成函数。由于 ,可见或{［n］k}的生成函数为(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={r1·e1,r2·e2,…,rm·em}，且r1+r2+…+rm=n，则S的k可重排列数Pk对应序列{Pk}的指数型生成函数为

其中，k可重排列数Pk为Ge(x)展开式中xk/k!的系数(k=0,1,2,…)。

例13个红球，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={r1·e1,r2·e2,…,rm·em}，则S中元素的k（无限）可重排列数Pk对应序列{Pk}的指数型生成函数为其中，k排列数Pk为xk/k!的系数mk。

推论4

特别地，若每个元素ei至少出现一次（这时有k≥n），则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,ai≡ai

B(x)=ebx,bi≡bi

cn=(a+b)n,ai≡ai,bi≡bi

后一式表示将(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)，如下所示：k12345

f(k)182764125

Δf(k)7193761

Δ2f(k)121824

Δ3f(k)66

Δ4f(k)0于是f(1)=1,Δf(1)=7,Δ2f(1)=12,Δ3f(1)=6,Δ4f(1)=Δ5f(1)=…=0应用求和公式即得

推论5

设S={r1·e1,r2·e2,…,rm·em}，若要求元素ei至少取ki个（ki≥0），则这种排列数形成序列的生成函数为

推论6

设S={r1·e1,r2·e2,…,rm·em}，且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}对应的指数型生成函数为故例4

注意到故是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可见,［x］n是第一类Stirling数skn的寻常生成函数，［x］n是|skn|的寻常函数。两类Stirling数是沟通xn,［x］n,［x］n这三种首项为1的多项式的桥梁。3.5Catalan数列与Stirling数列的生成函数

定义1

空集或有限点集T，满足：

(1)有一特定结点r称为“根”；

(2)删除根r，则剩下的点T\{r}组成两棵子二叉树：Tl（左子树）及Tr(右子树)。3.5.1Catalan数列的生成函数例1

二叉树（或二元树）的计数问题。例如，3个结点可有5棵不同的二叉树,如图3.5.1所示。图3.5.1二叉树

一般地，设cn为n个结点的不同的二叉树的个数，则有c0=1。在n＞0的情形下，二叉树有一个根结点及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(n≥2)边的凸多边形，若用连接不交对角线的方法把该多边形进行三角剖分，求所有不同的剖分方案数。

解令hn表示将n+1(n≥2)边凸多边形进行三角形剖分的方案数，则当n=1时，h1=1，当n≥3时，任取多边形一边记作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.2Stirling数列的生成函数为醒目起见，把第一类与第二类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项的一般形式为

其中，ni≥0(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+11·21+11·31+21·31

=1+4+9+2+3+6=25

Fibonacci数列，Catalan数列及Stirling数列形成组合数学中三种典型的数列，实际应用中许多组合计数结果都与它们相同或相似。3.6分配问题3.6.1盒子不相同的分配问题命题1

有n个相同的球，m个不同的盒子，各盒的容量分别为ni(ni≥0,i=1,2,…,m)。则其分配序列的寻常生成函数为

证明本命题与3.3节中的命题是一样的。这里可将m个盒子看成m个元素，记为e1,e2,…,em，n个相同的球中分别有:x1个球放入e1，即e1被选取x1次，x1≤n1；x2个球放入e2，即e2被选取x2次，x2≤n2；

…

xi个球放入ei，即ei被选取xi次，xi≤ni；

…

xm个球放入em，即em被选取xm次，xm≤nm。以上放法可记为：e1…e1

e2…e2

…

ei…ei

…

em…em

x1个x2个xi个xm个

且x1+x2+…+xm=n,0≤xi≤ni,i=1,2,…,m。以上放法仅与ei的出现次数有关，而不考虑ei的顺序。因此，满足命题条件的分配问题可归结为多重集S={n1·e1,n2·e2,…,ni·ei,…,nm·em}的n-可重组合问题，故其生成函数与3.3节命题相同。

推论1

若各盒容量ni=1(i=1,2,…,m)，球数n≤m，则其分配序列的生成函数为(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，其分配方案数是n-m为偶数n-m为奇数

命题2

有n个不同的球，m个不同的盒子，各盒的容量ni(ni≥0,i=1,2,…,m)。则其分配序列的指数型生成函数为

证明将n个不同的球放入m个不同的盒子（盒子加有编号），每次不同的放法可按如下方式记录。用b1,b2,…,bn表示n个不同的球，用e1,e2,…,em表示m个不同的盒子。b1b2…bn——n个不同的球已按某种顺序排好j1j2…jn——各球所占盒子的编号(反映于下标)其中ji∈{1,2,…,m}(i=1,2,…,n)。对球的分配不同，排列j1j2…jn也就不同；反之，不同的排列j1j2…jn对应了球的不同分配。而这种排列正是m个元素的n-可重排列。其中每个元素的重复次数分别是n1,n2,…,nm。从而问题归结为集合S={n1·e1,n2·e2,…,nm·em}的n-可重排列。故其生成函数为

推论1

若各盒的容量ni=1(i=1,2,…,m)，则其分配方案数为P(m,n)(n≤m)，其生成函数为

推论2

若各盒容量ni≥0且n1+n2+…+nm=n，则其分配方案数为n!/(n1!n2!…nm!)。其生成函数为推论3

若各盒容量不加限制，则其分配序列的生成函数为显见其分配方案数为mn。

推论4

若各盒非空（即ni≠0,i=1,2,…,m）。分配方案数为A(n,m)=m!S(n,m)。且分配序列的生成函数为(ex-1)m。

推论5

若指定r个盒非空，其余m-r个盒的容量不加限制，则其总的分配方案数为

证明不妨假定前r个盒非空，其中放入k个球(r≤k≤n),则因由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个以上的空盒，则其分配方案数为证明空盒数s≥r，与非空盒数m-s取法对应罗列如下：空盒数s=r,r+1,…,m-1，m

非空盒数m-s=m-r,m-(r+1),…,1,0

以上每组对应的分配方案数可分为两步计算：设有m-k个盒非空(r≤k≤n)，则（1）从m个盒中任取m-k个非空盒的选法数为

（2）

n个球放到m-k个非空盒中，据推论4，其分配方案数为A(n,m-k);

（3）由乘法原理，每种情况的分配方案数为A(n,m-k)。

注意到k=m时A(n,0)=0，故总的分配方案数为

若干个染有颜色的球，同色球看作一个类，同类中的球视为是相同的。若恰有1个球的颜色有k1种，恰有2个球的颜色有k2种，…，恰有s个球的颜色有ks种，可将所有球分类的型记为k1

·1+k2

·2+…+ks

·s

或者记为例如，14个球染有赤、橙、黄、绿、青、蓝、紫7种颜色，即分为7个类，且各种颜色相应的数量分别为2，1，3，2，1，2，3，则这14个球分类的型为12×23×32。

命题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部分的无序拆分，n≥m。(其证明参见随后几节。)

命题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个球,1≤t≤n）；或者将其看作n元集X的划分（无空盒子）的型，每个型对应于适合条件：及a1≥a2≥a3≥…≥am≥1的一个m元组(α1,α2,…,αm)。该m元组通常就称为整数n的一个拆分。整数n分成恰有m个类（或称非零部分）的拆分个数，记作Pmn。例如：整数n

拆分方式 拆分个数

2 2,1+13,3,2+1,1+1+14,4,3+1,2+22+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）对a′∈E′

a∈E

使φ(a)=a′可见,φ为一双射函数。因此第二个公式直接从定义可得。推论注意到j＞n时有Pjn=0,故对k＞n有利用命题1及其推论给出的公式，可递归地推算Pmn如下：Pmn

m=123456

n=11

211

3111

41211

512211

6133211

·

求拆分三角的算法:

№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;n2

min(j,n1);

对t=1,n2,S

S+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.15+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分成各类都不相等且都是奇数的拆分的个数。

证明设 ,其中n1＞n2＞…＞nk。显见这是一个把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，显见有ni≠nj；若s≠t（不妨设t＞s）,但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.8n的拆分数Pn的生成函数命题1

n的拆分数Pn的生成函数是证明只需证事实上，当|x|<1时，有

在xn的系数中，第一项确定n的一个拆分，即1+1+…+1+2+2+…+2+…+k+k+…+k=n

λ1

λ2

λk

最后，取a1=a2=…=1，即得上述公式。命题2Pnm的生成函数是命题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节命题5，上述等式的展开式中，xn的系数显然等于

例1

有1、2、3、4克的砝码各一枚，问能称出哪几种重量？对能称出的重量有几种可称量方案？

解

从G(x)展开式中x的幂次知，可称出1~10克的重量，系数即为对应的称量方案数。如对2x5项，即称量5克的方案有两种： 5=3+2=4+1

同样，有

6=1+2+3=4+2，10=1+2+3+4

故称出6克的方案数有两种，称出10克的方案数是唯一的。

例2

求用1角，2角，3角的邮票贴出不同数值的方案数。

解因邮票允许重复，故生成函数为

以x4为例，其系数为4，即4拆分成1、2、3之和的拆分数为4，拆分方案为4=1+1+1+1，4=1+1+2，4=2+2，4=1+3

例3

若有1克的砝码3枚，2克的砝码4枚，4克的砝码2枚。问能称出哪些重量？有几种方案？解G(x)=(1+x+x2+x3)(1+x2+x4+x6+x8)(1+x4+x8)=(1+x+x2+2x3+2x4+2x5+2x6+2x7+2x8+2x9+x10+x11)

·(1+x4+x8)

=1+x+2x2+2x3+3x4+3x5+4x6+4x7+5x8+5x9+5x10+5x11

+4x12+4x13+3x14+3x15+2x16+2x17+x18+x19

观察展开式各项中x的幂次及其系数即知答案。

例4

整数n拆分成1，2，3，…,m的和，并允许重复，求其生成函数。若其中m至少出现一次，其生成函数如何？

解当n允许重复地拆分成1，2，…，m的和时，其生成函数若拆分中m至少出现一次，其生成函数显见G2(x)=G1(x)-(1-xm)·G1(x)=xm·G1(x)其组合意义是：n拆分成1,2,…,m的和的拆分数，减去n拆分成1,2,…,m-1的和的拆分数，即为至少出现一个m的拆分数。

例5

设有1、2、4、8、16、32克砝码各一枚，问能称出哪些重量？分别有几种方案？

解

由生成函数知，用给定的砝码能称出从1克到63克的各种重量，且其方案都是唯一的。3.9整数n分为以h为最小类的拆分数

以Pn表示n的拆分数；Pmn表示n分成m个类的拆分数；Pn,h表示n分成以h为最小类的拆分数；Pmn,h表示n分成m个类且以h为最小类的拆分数。则显见有

命题1

例考虑把6分成m个类，并以h为最小类的拆分。各拆分可用三元树结构存贮,如图3.9.1所示。图3.9.1三元树结构n-m=(a1-1)+(a2-1)+…+(am-1-1)+(h-1)而当h=1时，拆分n=a1+a2+…+am联系着拆分n-1=a1+a2+…+am-1

命题2

当h＞1时 当h=1时，。

证明设h＞1，则适合a1≥a2≥…≥am=h的每个拆分n=a1+a2+…+am就联系着如下的拆分：命题3Pn,h=Pn-h,h+Pn-h,h+1+…证明因为n=(n-h)+h,所以命题4

递归关系:当h＞1时当h=1时证明设h＞1，由命题3比较命题3，可得Pn,h=Pn-1,h-1-Pn-h,h-1