《指数生成函数》PPT课件.ppt

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