第5章-生成函数-数模讲座48

Chapter5

生成函数§1

生成函数简介一.定义1.例1：a,b,c三个球，现从中选球：取1个球：a+b+c取2个球：ab+bc+ca取3个球：abc多项式表示：(1+ax)(1+bx)(1+cx)=1+(a+b+c)x+(ab+bc+ca)x2+(abc)x3注：(1)xk的系数为从三个数中选取k个的方法之形象表示

(2)(1+ax)可表为对球a或不选或选例2.两个色子掷出6点，有多少种掷法？把色子出现的点数1,2,…6和t,…,t6对应起来这种对应把组合问题的加法法则和幂级数的t的乘幂的相加对应起来。故使两个色子掷出6点的方法数等价于求生成函数的思想—把离散数列和幂级数一一对应起来，把离散数列间的相互结合关系对应成为幂级数间的运算关系，最后由幂级数形式来确定离散数列的构造.进一步：10个色子掷出30点，有多少种掷法？注：(1)数列可有限可无限(2)只是形式幂级数(3)x可换做别的g(x)，只是标志函数二.数列与幂级数的运算2.代数运算：3.分析运算：4.柯西乘积：注：(1)称{cn}为数列{an}与{bn}的柯西乘积，记为{cn}={an}*{bn}(2)此即幂级数运算中的乘法部分三.几个常见数列的生成函数四.应用1.应用之一：组合恒等式的证明2.应用之二：求数列的前n项之和(n≥0)3.应用之三：求解递推关系4.应用之四：计算重复组合数一.定义1.问题：考虑如下不定方程(*)的非负整数解的个数：x1+…+xk=n,xi∈Si,(i=1,…,k)

注：此即从k种不同的元素中重复取n个，使得第i个元所取个数∈Si(i=1,…,k)的个数

注：当k个子集Si取定时，此即一个数列{cn}注：(1).此即用生成函数去求解重复组合数(2).思路：第一步：根据限制集Si求出生成函数第二步：展开成幂级数第三步：求出系数an即得二.实例解：此即所有Si为非负整数集合N0例2：从一堆水果中选出n个，使得苹果数为偶数，香蕉数为5的倍数，桔子数不超过4个(可为4)，梨子数或0或1，求选出n个的选法数.故：an=n+1.例3:任一正整数n，均可表示为的形式，且表示法唯一.一.思考：为何会利用指母函数？2.现排列数P(n,k)在上述形式下不易化简！但P(n,k)=C(n,k)k!，故而：§2指数型生成函数二.几个常见数列的指母函数：三.应用指母函数求解重复排列问题注：(1)证明中先将重复度固定3：定理3：(2)带限制条件的重复排列可由此解决五.实例解：此即所有Si=N0的情况解：此即Si={0,1,...,ni},i=1,2,...,k的情况例4:

求1，3，5，7，9五个数字组成的n位数的个数an，要求其中3，7出现的次数为偶数，其他1，5，9出现次数不加限制.§3分配问题一.简介1.问题：将n个球放到r个盒中的放法问题2.考虑因素：(1).球是否相同(2).盒子是否相同(3).是否允许有空盒(4).不考虑球在盒子内部的顺序(5).不限制盒子的容量二.情况讨论Proof：此即n元集的无序r划分Proof：分类，设有i个非空盒子即可Proof：先设盒子相同，再对盒子排列即可Proof：每个球有r种选择注：(1)此即n元集X到r元集Y的映射的个数附录：Stirling数简介1.两组多项式的互相表出：{(x)0,(x)1,…,(x)n}与{x0,x1,…,xn}注:(1)s(i,j)即称为第一类Stirling数(2)易见：s(n,0)=0,(n≥1);s(n,n)=12.反之：注:(1)S(i,j)即称为第二类Stirling数(2)易见：S(n,0)=0,(n≥1);S(n,n)=13.矩阵表示注:(1)此两类Stirling数均与x无关(2)两类矩阵均为对角元全1的下三角阵(3)