《指数生成函数》PPT课件.ppt
2.4 指数生成函数,2.4.1 指数生成函数的定义2.4.2 指数生成函数的运算2.4.3 指数生成函数ex2.4.4 指数生成函数展开式2.4.5 不同球分配到不同盒2.4.6 不同球分配到相同盒2.4.7 相同球分配到相同盒？,2.4.1 生成函数的定义,定义设x是一个抽象符号，an(n0,1,2,)为实数列，若函数F(x)可表示成F(x)a0 a1 a2 称F(x)为数列an(n0,1,2,)的指数生成函数(exponential generating functions),2.4.2 指数生成函数的运算,指数生成函数是生成函数(1)(2)()(),2.4.3 指数生成函数ex,序列1,1,1,1,的指数生成函数为 ex 序列a01,a1,a2,an,(a是实数)的指数生成函数是 eaxa0 a1 a2 an,2.4.3 指数生成函数ex,数列1,1,1,的指数生成函数ex 具有与指数相似的性质：exey ex+y，这是因为 exey()()()()ex+y 特别地，exe-xe01，从而ex,2.4.4 指数生成函数展开式,(1)ex(2)eaxa0 a1 a2 an(3)(4),2.4.5 不同球分配到不同盒,例 把5个不同球放入a1,a2,a3这3个不同盒中，盒a1中最少放1个且最多放3个，盒a2中只能放偶数个，盒a3中只能放奇数个，讨论其不同方案数h5解三个不同盒a1,a2,a3依次对应3个圆括号,做 F(x)()()(),2.4.5 不同球分配到不同盒,做重集2a1,2a2,1a3 全排列a3a1a2a1a2 1 2 3 4 5 盒 a1 a2 a3 球(2,4)(3,5)(1),全排列数,2.4.5 不同球分配到不同盒,做重集2a1,3a3 全排列a1a3a3a1a3 1 2 3 4 5 盒 a1 a2 a3 球(1,4)()(2,3,5),全排列数,2.4.5 不同球分配到不同盒,符合题意的方案数h5 F(x)的展开式中 项的系数,2.4.5 不同球分配到不同盒,定理设重集M1a1,M2a2,Mkak,其中Mi(正整数或)(i1,2,k)为元素ai的重数。重集的r排列数记作br，则序列br(r0,1,2,)(b01)的指数生成函 数为F(x),2.4.5 不同球分配到不同盒,定理 把r个不同球放入k个不同盒子a1,a2,a3,ak中，限定盒子的容量集合为Mi(i1,2,k)，则其分配方案数序列br(r0,1,2,)(b01)的指数生成函数为F(x),2.4.5 不同球分配到不同盒,例 求由1,3,5,7,9这五个数字组成的25位数的个数，要求1和3都出现偶数次，5,7,9出现的次数均不限。解 问题即把25个不同球放到标号为1,3,5,7,9五个不同盒中，且盒1和3中均放偶数个，盒5,7,9的容量均不限。设满足此例条件的n位数的个数为 an，则an(n0,1,2,)的指数生成函数为,2.4.5 不同球分配到不同盒,F(x),2.4.5 不同球分配到不同盒,所以a25,2.4.5 不同球分配到不同盒,例 解例令g(m,n)为由m个元素集合A到n个元素集合B的满射的个数(mn)，则g(m,n),2.4.5 不同球分配到不同盒,证明设Aa1,a2,am，B1,2,n，即把m个不同球a1,a2,am放入标号为1,2,n这n个不同盒中，且每盒中至少要放一个，故g(m,n)(m0,1,2,)的指数生成函数为,2.4.5 不同球分配到不同盒,故,2.4.6 不同球分配到相同盒,问题：把r个不同球放入k个相同盒里，盒的容量可限定，求其分配方案数ar,2.4.6 不同球分配到相同盒,把r个不同球放入k个不同盒里，盒的容量可限定，已能很容易地求出其分配方案数 另一方面，把r个不同球放入k个不同盒里，盒的容量可限定，又可分为两步完成：先把r个不同球放入k个相同盒里，盒的容量可以限定，其分配方案数为ar；再把这k个盒编号，即对这k个盒做全排列，有k!种方案。由乘法原则，有 ark!,2.4.6 不同球分配到相同盒,例 解例 把2n个人分成n组，每组2人，有多少种不同的分组方法？解 问题等价于：把2n个不同球放入n个相同盒里，每盒2个，求其分配方案数a2n,2.4.6 不同球分配到相同盒,把2n个不同球放入n个不同盒里，每盒2个，其分配方案数(n0,1,2,)的生成函数 即 又,2.4.7 相同球分配到相同盒？,问题：把r个相同球放入k个相同盒里，盒的容量可限定，求其分配方案数ar,2.4.7 相同球分配到相同盒？,把r个相同球放入k个不同盒里，盒的容量可限定，已能很容易地求出其分配方案数 另一方面，把r个相同球放入k个不同盒里，盒的容量可限定，又可分为两步完成：先把r个相同球放入k个相同盒里，盒的容量可以限定，其分配方案数为ar；再把这k个盒编号，即对这k个盒做全排列，有k!种方案。由乘法原则，有 ark!？,2.4.7 相同球分配到相同盒？,步(1)把9个相同球放入5个相同盒,例如一个盒中放5个,其余四个盒中各放1个,记为(5)(1)(1)(1)(1)步(2)将5个相同盒编号(5)(1)(1)(1)(1)(1)(5)(1)(1)(1)(1)(1)(5)(1)(1)(1)(1)(1)(5)(1)(1)(1)(1)(1)(5),步(1)把9个相同球放入5个相同盒中,例如三个盒中各放1,其余两个盒中各放3个,记为(1)(1)(1)(3)(3)步(2)将5个相同盒编号(1)(1)(1)(3)(3)(1)(1)(3)(1)(3)(1)(3)(1)(1)(3)(3)(1)(1)(1)(3)(1)(1)(3)(3)(1)(1)(3)(1)(3)(1)(3)(1)(1)(3)(1)(1)(3)(3)(1)(1)(3)(1)(3)(1)(1)(3)(3)(1)(1)(1),随堂作业,例 设n为偶数，用an表示长为n且含偶数个0偶数个1的二进制序列的个数，求an,解 把长为n的二进制序列的n个位置看作n个不同球，将它们放入标号为0和1两个不同盒中，且每盒中均放偶数个，于是数列an(n0,1,2,)的指数生成函数为,
