母函数与指数型母函数ppt课件

1、第二章第二章 母函数与递推关系母函数与递推关系2.1 母函数与指数型母函数母函数与指数型母函数2.2 递推关系与递推关系与Fibonacci数列数列2.3 线性常系数递推关系线性常系数递推关系2.4 非线性递推关系举例非线性递推关系举例2.5 运用举例运用举例2.1 母函数与指数型母函数母函数与指数型母函数 母函数母函数 母函数的性质母函数的性质 整数的拆分整数的拆分 Ferrers 图像图像 指数型母函数指数型母函数1. 母函数母函数母函数方法是一套非常有用的方法，运用极广。母函数方法是一套非常有用的方法，运用极广。这套方法的系统表达，最早见于这套方法的系统表达，最早见于Laplace在在1

2、812年年的名著的名著概率解析实际。概率解析实际。我们来看如下的例子：两个骰子掷出我们来看如下的例子：两个骰子掷出6点，有多少点，有多少种选法？种选法？留意到，出现留意到，出现1，5有两种选法，出现有两种选法，出现2，4也有两也有两种选法，而出现种选法，而出现3，3只需一种选法，按加法法那只需一种选法，按加法法那么，共有么，共有2+2+1=5种不同选法。种不同选法。或者，第一个骰子除了或者，第一个骰子除了6以外都可选，有以外都可选，有5种选法，种选法，一旦第一个选定，第二个骰子就只需一种能够的选一旦第一个选定，第二个骰子就只需一种能够的选法，按乘法法那么有法，按乘法法那么有51=5种。种。但碰

3、到用三个或四个骰子掷出但碰到用三个或四个骰子掷出n点，上述两方法就点，上述两方法就不胜其烦了。不胜其烦了。想象把骰子出现的点数想象把骰子出现的点数1,2,6和和t,t2,t6对应起来对应起来，那么每个骰子能够出现的点数与，那么每个骰子能够出现的点数与(t+t2+t6)中中t的的各次幂一一对应。各次幂一一对应。假设有两个骰子，那么假设有两个骰子，那么(.)(.).2626234562345ttttttttttt 其中其中t6的系数为的系数为5，显然来自于，显然来自于, ,.156246336426516ttttttttttttttt 这阐明，掷出这阐明，掷出6点的方法一一对应于得到点的方法一一对

4、应于得到t6的方法。的方法。262( )(.)f tttt故使两个骰子掷出故使两个骰子掷出n点的方法数等价于求点的方法数等价于求中中tn的系数。的系数。这个函数这个函数f(t)称为母函数。称为母函数。母函数方法的根本思想：母函数方法的根本思想：把离散数列和幂级数一一对应起来，把离散数列间把离散数列和幂级数一一对应起来，把离散数列间的相互结合关系对应成为幂级数间的运算关系，最的相互结合关系对应成为幂级数间的运算关系，最后由幂级数方式来确定离散数列的构造。后由幂级数方式来确定离散数列的构造。再来看下面的例子：再来看下面的例子：121221213112(1)(1)(1)1()(),nnnnnna x

5、a xa xaaaxa aa aaaxa aa x 假设令假设令a1=a2= =an=1，那么有，那么有()( , )( , )( , ).21112nnxC nxC nxC n n x 这就是二项式展开定理。这就是二项式展开定理。 () ()()111mnm nxxx ( , )( , )( , ) (, )(, )(,)(, )(, )(,)010101nmmnC nC nxC n n xC mC mxC m m xC mnC mnxC mn mn x 比较等号两端项对应系数，可以得到恒等式：比较等号两端项对应系数，可以得到恒等式：(, )(, ) ( , ) (, ) ( ,) (, )

6、 ( , ).0110C mn rC mC n rC mC n rC m r C n () (/)()1111nmmm nxxxx ( , )( , )( , ) (, )(, )(,) (, )(, )(, ) (,)120101012nmmm nC nC nxC n n xC mC mxC m m xxC mnC mnxC mnxC mn mn x (,)( , ) (, )( , ) (, ) ( ,) (,). 0011C mn mC nC mC nC mC n m C m m 比较等式两端的常数项，可以得到恒等式：比较等式两端的常数项，可以得到恒等式：(1)( ,0)( ,1)( ,

7、 )nnxC nC nxC n n x中令中令x=1 可得可得又如在等式又如在等式( ,0)( ,1)( ,2)( , )2 .nC nC nC nC n n两端对两端对x求导可得：求导可得：()( , )( , )( , ),111122nnnxC nC nxnC n n x 再令再令x=1 可得可得1( ,1)2 ( ,2)3 ( ,3)( , )2.nC nC nC nnC n nn类似还可以得到类似还可以得到222( ,1)2( ,2)( , )(1)2.nC nC nn C n nn n还可以类似地推出一些等式，但经过上面一些例子还可以类似地推出一些等式，但经过上面一些例子已可见函数

8、已可见函数(1+x)n在研讨序列在研讨序列C(n,0),C(n,1),C(n,n)的关系时所起的作用。的关系时所起的作用。定义：对于序列定义：对于序列a0,a1,a2,，函数，函数2012( )G xaa xa x 称为序列称为序列a0,a1,a2,的母函数。的母函数。例如函数例如函数(1+x)n就是序列就是序列C(n,0),C(n,1),C(n,n)的的母函数。母函数。如假设知序列，那么对应的母函数可根据定义给出如假设知序列，那么对应的母函数可根据定义给出。反之，假设曾经求出序列的母函数反之，假设曾经求出序列的母函数G(x)，那么该序，那么该序列也随之确定。列也随之确定。DDD输入输入u输出

9、输出v例例1 以下图是一逻辑回路，符号以下图是一逻辑回路，符号D是一延迟安装，是一延迟安装，即在时间即在时间t输入一个信号给延迟安装输入一个信号给延迟安装D，在，在t+1时辰时辰D将输出同样的信号，符号将输出同样的信号，符号表示加法安装。表示加法安装。假设在假设在t=0,1,2,时辰的输入为时辰的输入为u0,u1,u2,求在这些求在这些时辰的输出时辰的输出v0,v1,v2,显然，显然，,12201100uuvuuvuv。,0233uuuv普通的有普通的有. 3 ,31nuuuvnnnn假设信号输入的序列假设信号输入的序列u0,u1,的母函数为的母函数为U(x)，输，输出的信号序列出的信号序列v

10、0,v1,的母函数为的母函数为V(x)，那么，那么3( )(1) ( )( ) ( ),V xxx U xP x U x 其中其中( )P xxx 31被安装的特性所确定，称为该安装的传送函数。被安装的特性所确定，称为该安装的传送函数。设设r，w，y 分别代表红球，白球，黄球。分别代表红球，白球，黄球。2(1)(1)(1)rrwy 例例2 有红球两个，白球、黄球各一个，试求有多少种有红球两个，白球、黄球各一个，试求有多少种不同的组合方案。不同的组合方案。22221()() ().rywrryrwywr yr wrywr yw (1) 取一个球的组合数为取一个球的组合数为3，即分别取红，白，黄。

11、，即分别取红，白，黄。(2) 取两个球的组合数为取两个球的组合数为4，即两个红的，一红一黄，即两个红的，一红一黄，一红一白，一白一黄。一红一白，一白一黄。(3) 取三个球的组合数为取三个球的组合数为3，即两红一黄，两红一白，即两红一黄，两红一白，一红一黄一白。一红一黄一白。(4) 取四个球的组合数为取四个球的组合数为1，即两红一黄一白。，即两红一黄一白。22( )(1)(1)G xxxx 共有共有1+3+4+3+1=12种组合方式。种组合方式。43210,cccccrc令取令取r的组合数为的组合数为 ,那么序列那么序列的母函数为的母函数为2341343.xxxx 令令an为从为从8位男同志中抽

12、取出位男同志中抽取出n个的允许组合数。由个的允许组合数。由于要男同志的数目必需是偶数。故于要男同志的数目必需是偶数。故例例3 某单位有某单位有8个男同志，个男同志，5个女同志，现要组织一个女同志，现要组织一个由数目为偶数的男同志和数目不少于个由数目为偶数的男同志和数目不少于2的女同志的女同志组成的小组，试求有多少种组成方式？组成的小组，试求有多少种组成方式？2468( )1287028.A xxxxx 因此序列因此序列a1,a2,a8对应的母函数为：对应的母函数为：1357020,1,(8,2)28,aaaaaaC 468(8,4)70,(8,6)28,1.aCaCa 类似可得女同志的允许组合

13、数对应的母函数为类似可得女同志的允许组合数对应的母函数为2345( )10105.B xxxxx( )( ) ( ) () ()C xA x B xxxxxxxxx 24682345128702810105 xxxxxxxxxxxx23456789101112131010285281840728630350150385其中其中xk的系数就是组成符合要求的的系数就是组成符合要求的k人小组的数目。人小组的数目。2. 母函数的性质母函数的性质设序列设序列ak, bk对应的母函数分别为对应的母函数分别为A(x), B(x)。那么下面的两个性质显然成立：那么下面的两个性质显然成立：(1) A(x)= B

14、(x) 当且仅当当且仅当 ak= bk。(2) 假设假设A(x)+B(x)=c0+c1x+c2x2+，那么，那么ck=ak+bk。性质性质1：假设：假设 那么那么 B(x)=xlA(x)。0,kk lklbakl ( ) ( ).11101000lllllllB xb xbxa xa xx A x 证证:那那么么( )().!1211123mmmmxxxxB xxe 例例4 知知 ,!231123xxxxA xe性质性质2：假设：假设bk=ak+l，那么，那么( ) ( )/.lklkkB xA xa xx 10那那么么( ).!xxxxB xexx 2221234例例5 知知 ,!23112

15、3xxxxA xe 性质性质3：假设：假设bk=a0+ak，那么，那么( )( ).A xB xx 1ba 00baa101baaa 2012kkbaaaa 0121:x:x2:xk:_ ( )/()/()/()B xaxa xxa xx 2012111/()( )/().aa xa xxA xx 201211+)那那么么( )B xxxx 231234例例6 知知( ),nA xxxxx 2111( ),()A xxx2111( )C xxxx 2313610( ).()B xxx3111性质性质4：假设：假设bk=ak+ak+1+，那么，那么( )( )( ).AxA xB xx 11ba

16、aa 0012( )baaaAa 112301( )baaaAaa 22340111:x:x2:_ ( )( )()() ()B xAxxa xxxa xxx 2202211 111()( )( )( ).aa xxAAxA xxxx 0111111+)( )A 1性质性质5：假设：假设bk=kak，那么，那么( )( ).B xxA x 性质性质6：假设：假设bk=ak/(1+k)，那么，那么( )( ).xB xA x dxx 01那那么么( )B xxxx 2323例例7 知知( ),nA xxxxx 2111 .()xxxx 21 11性质性质7：假设：假设ck=a0bk+a1bk-1

17、+ak-1b1+akb0，那么，那么( )C xcc xc x2012( ) ( ).A x B x ca b 000ca ba b10 110ca ba ba b 2021 1201:x:x2:_ C xabb xb xa x bb xb xa xbb xb x 2200121012222012 ( ) ( ).aa xa xbb xb xA x B x 22012012+)令令 ,xB xxxxx 232231例例8 知知( ),nA xxxxx 2111(),kknk nnk kca bk 01122( )( ) ( ).()xC xA x B xx 31那那么么3. 整数的拆分整数的拆

18、分所谓正整数拆分即把正整数分解成假设干正整数的和。所谓正整数拆分即把正整数分解成假设干正整数的和。相当于把相当于把n个无区别的球放到个无区别的球放到n个无标志的盒子，盒个无标志的盒子，盒子允许空着，也允许放多于一个球。子允许空着，也允许放多于一个球。整数拆分成假设干整数的和，方法不一，不同拆分整数拆分成假设干整数的和，方法不一，不同拆分法的总数叫做拆分数。法的总数叫做拆分数。拆分可以分为无序拆分和有序拆分；不允许反复的拆分可以分为无序拆分和有序拆分；不允许反复的拆分和允许反复的拆分。拆分和允许反复的拆分。例例9 假设有假设有1克、克、2克、克、3克、克、4克的砝码各一枚，问克的砝码各一枚，问能

19、称出那几种分量？有几种能够方案？能称出那几种分量？有几种能够方案？()()()()xxxx 2341111.xxxxxxxxxx2345678910122222从右端的母函数知可称出从从右端的母函数知可称出从1克到克到10克，系数便是克，系数便是方案数。方案数。例如右端有例如右端有2x5项，即称出项，即称出5克的方案有克的方案有2种：种：5=2+3=1+4。类似的，称出类似的，称出6克的方案也有克的方案也有2种：种：6=2+4=1+2+3。例例10 求用求用1分、分、2分、分、3分的邮票贴出不同数值的方分的邮票贴出不同数值的方案数。案数。()()()xxxxxx 22436111以以x4为例，

20、其系数为为例，其系数为4，即，即4拆分成拆分成1，2，3之和的允之和的允许反复的拆分数为许反复的拆分数为4：4 = 1+1+1+1 = 1+1+2 = 1+3 = 2+2。留意邮票允许反复，因此母函数为：留意邮票允许反复，因此母函数为：例例11 假设有假设有1克砝码克砝码3枚、枚、2克砝码克砝码4枚、枚、4克砝码克砝码2枚枚，问能称出那几种质量？各有几种方案？，问能称出那几种质量？各有几种方案？G xxxxxxxxxx 23246848( )(1)(1)(1)即可称出即可称出1至至19克的质量，不同的方案数即为对应项克的质量，不同的方案数即为对应项前面的系数。前面的系数。母函数为：母函数为：x

21、xxxxxxxxxxxxxxxxxx 2345678910111213141516171819 1223344 555544 3322.例例12 把整数把整数N无序拆分成整数无序拆分成整数a1,a2,an的和，且的和，且不允许反复，求不同的拆分数。不允许反复，求不同的拆分数。的不同解的个数。的不同解的个数。这个问题对应于求不定方程这个问题对应于求不定方程 ., , , ,. ,nnia xa xa xNxin 11220 11 2令令bN表示不同的拆分数，那么其对应的母函数为：表示不同的拆分数，那么其对应的母函数为：( )()().().naaaG xxxx12111特殊的，当特殊的，当ai=

22、i时，对应的母函数为：时，对应的母函数为：( )()().().nG xxxx 2111例例13 把整数把整数N无序拆分成整数无序拆分成整数a1,a2,an的和，允的和，允许反复，求不同的拆分数。许反复，求不同的拆分数。的不同解的个数。的不同解的个数。这个问题对应于求不定方程这个问题对应于求不定方程 ., , , ,. ,nnia xa xa xNxin 11220 11 2令令bN表示不同的拆分数，那么其对应的母函数为：表示不同的拆分数，那么其对应的母函数为：( )(.)(.) . (.)nnaaaaaaG xxxxxxx 1122222111.( -)() . ()naaaxxx 1211

23、11特殊的，当特殊的，当ai=i时，对应的母函数为：时，对应的母函数为：( ).()().()nG xxxx 21111( )(.)(.) . (.)nnaaaaaaG xxxxxxx 1122222111例例14 把整数把整数N无序拆分成奇整数的和，允许反复，无序拆分成奇整数的和，允许反复，求不同的拆分数。求不同的拆分数。这相当于在上例中把这相当于在上例中把ai取成奇数，因此拆分数对应取成奇数，因此拆分数对应的母函数为：的母函数为：( ) .()()()nGxxxx 03211111例例15 把整数把整数N无序拆分成无序拆分成2的幂次的和，求不同的拆的幂次的和，求不同的拆分数。分数。这相当于

24、把这相当于把N拆分成拆分成1,2,4,8,的和，但不允许反复。的和，但不允许反复。因此拆分数对应的母函数为：因此拆分数对应的母函数为：( )()()()()ntG xxxxx 2421111例例16 把整数把整数N无序拆分无序拆分1,2,m的和，允许反复，的和，允许反复，求不同的拆分数。假设要求求不同的拆分数。假设要求m至少出现一次呢？至少出现一次呢？假设无要求，由例假设无要求，由例13可知其母函数为：可知其母函数为：( ).()()()mmGxxxx 21111假设要求假设要求m至少出现一次，那么拆分数对应的母函至少出现一次，那么拆分数对应的母函数为：数为： mmmGxxxxxxx2242(

25、 )(1)(1)()mmxxxx2.(1)(1)(1)这个等式的组合意义很明显：整数这个等式的组合意义很明显：整数n拆分成拆分成1到到m的的和的拆分数减去拆分成和的拆分数减去拆分成1到到m-1的和的拆分数，即的和的拆分数，即为至少出现一个为至少出现一个m的拆分数。的拆分数。显然有显然有 mmmGxxxxxxx2211( )(1)(1)(1)1(1)(1)(1) mmGxGx 1( )( ).( )()()()nG xxxx2111设设bN表示表示N剖分成不同正整数和的剖分数，那么其剖分成不同正整数和的剖分数，那么其对应的母函数为：对应的母函数为：定理定理1 整数剖分成不同整数的和的剖分数整数剖

26、分成不同整数的和的剖分数(不允许反不允许反复复)等于剖分成奇数的剖分数等于剖分成奇数的剖分数(允许反复允许反复)。xxxxxxxx 246823411111111 .()()nxxx 3211111( )()()()G xxxxxxx 22436111设设bN表示表示N剖分成反复数不超越剖分成反复数不超越2的正整数之和的的正整数之和的剖分数，那么其对应的母函数为：剖分数，那么其对应的母函数为：定理定理2 N剖分成其他数之和但反复数不超越剖分成其他数之和但反复数不超越2，其剖，其剖分数等于它剖分成不被分数等于它剖分成不被3整除的数的和的剖分数。整除的数的和的剖分数。xxxxxxxx 369122

27、3411111111.kkxxxxx 24531111111111不不整整除除( )()()()()ntG xxxxx 2421111定理定理3 N被剖分成一些反复次数不超越被剖分成一些反复次数不超越k次的整数的次的整数的和，其剖分数等于被剖分成不被和，其剖分数等于被剖分成不被k+1除尽的数的和除尽的数的和的剖分数。的剖分数。xxxxxx 24824111111xxxx 23111定理定理4 对恣意整数对恣意整数N，它被无序剖分成，它被无序剖分成2的幂次的和的幂次的和的剖分方式一定独一。的剖分方式一定独一。例例17 假设有假设有1、2、4、8、16克的砝码各一枚，问能克的砝码各一枚，问能称出那

28、几种质量？有几种能够方案？称出那几种质量？有几种能够方案？( ) ()()()()()G xxxxxx2481611111这阐明用这些砝码可以称出从这阐明用这些砝码可以称出从1克到克到31克的质量，而克的质量，而且方案都是独一的。且方案都是独一的。xxxxxxxxxx 2481632248161111111111xxxxx 3223111.1实践上这阐明整数的二进制表示是独一的。实践上这阐明整数的二进制表示是独一的。4. Ferrers图像图像一个从上而下的一个从上而下的n层格子组成的图像，层格子组成的图像，mi为第为第i层的层的格子数。格子数。当当mimi+1，即上层的格子数不少于下层的格子

29、数，即上层的格子数不少于下层的格子数时，称之为时，称之为Ferrers图像，如以下图：图像，如以下图：每一层至少有一个格子。每一层至少有一个格子。绕虚线轴旋转所得的图绕虚线轴旋转所得的图依然是依然是Ferrers图像。这图像。这样的两个样的两个Ferrers图像称图像称为一对共轭的为一对共轭的Ferrers图图像。像。(1) 整数整数n拆分成拆分成k个数的和的拆分数，与数个数的和的拆分数，与数n拆分成拆分成最大数为最大数为k的拆分数相等。的拆分数相等。由于整数由于整数n拆分成拆分成k个数的和的拆分可以用一个个数的和的拆分可以用一个k行行的图像表示。所得的的图像表示。所得的Ferrers图像的共

30、轭图像最上面图像的共轭图像最上面一行有一行有k个格子。例如：个格子。例如： 利用利用Ferrers图像可以得到一些关于整数拆分的结果：图像可以得到一些关于整数拆分的结果： 24=6+6+5+4+3 24=6+6+5+4+3 5 5个数，最大数为个数，最大数为6 6 24=5+5+5+4+3+2 24=5+5+5+4+3+2 6 6个数，最大数为个数，最大数为5 5理由和理由和(1)相类似。相类似。因此，拆分成最多不超越因此，拆分成最多不超越m个数的和的拆分数的母个数的和的拆分数的母函数是：函数是：(2) 整数整数n拆分成最多不超越拆分成最多不超越m个数的和的拆分数，个数的和的拆分数，与与n拆分

31、成最大不超越拆分成最大不超越m的拆分数相等。的拆分数相等。.()()()mxxx 21111正好拆分成正好拆分成m个数的和的拆分数的母函数为个数的和的拆分数的母函数为()()()()()()mmxxxxxx 22111111111.()()()mmxxxx 2111(3) 整数整数n拆分成互不一样的假设干奇数的和的的拆分成互不一样的假设干奇数的和的的拆分数，与拆分数，与n拆分成自共轭的拆分成自共轭的Ferrers图像的拆分图像的拆分数相等。数相等。设整数设整数n拆分为拆分为n=(2n1+1)+(2n2+1)+(2nk+1)，其，其中中n1n2nk。构造一个构造一个Ferrers图像，第一行第一

32、列都是图像，第一行第一列都是n1+1格，格，对应于对应于2n1+1，第二行第二列都是，第二行第二列都是n2+1格，对应于格，对应于 2n2+1，依此类推。，依此类推。这样得到的这样得到的Ferrers图像一定是自共轭的。图像一定是自共轭的。反过来，自共轭的反过来，自共轭的Ferrers图像也可以对应到一些不图像也可以对应到一些不同奇数的和。同奇数的和。例如例如17=9+5+3对应的对应的Ferrers图像为：图像为：(4) 正整数正整数n剖分成不超越剖分成不超越k个数的和的剖分数，等于个数的和的剖分数，等于将将n+k剖分成恰好剖分成恰好k个数的剖分数。个数的剖分数。不超越不超越k层的层的Fer

33、rers图像的每一层加上一个格子，图像的每一层加上一个格子，一一对应到一个刚好一一对应到一个刚好k层的层的Ferrers图像。图像。5. 指数型母函数指数型母函数思索思索n个元素组成的多重集，其中个元素组成的多重集，其中a1反复了反复了n1次，次，a2 反复了反复了n2次，次，ak反复了反复了nk次，次，n=n1+n2+nk。从中取。从中取r个陈列，求不同的陈列数个陈列，求不同的陈列数。假设假设r=n，即思索，即思索n个元素的全陈列，那么不同的陈个元素的全陈列，那么不同的陈列数为：列数为：!21knnnn但是对于普通的但是对于普通的r，情况就比较复杂了。，情况就比较复杂了。8765432325

34、43232232369109631 )1 ( )23321 ( )1)(1)(1 ()(xxxxxxxxxxxxxxxxxxxxxxxxxG 先看一个详细的问题：假设有先看一个详细的问题：假设有8个元素，其中个元素，其中a1反反复复3次，次，a2反复反复2次，次，a3反复反复3次。从中取次。从中取r个组合，个组合，其组合数为其组合数为cr，那么其对应的母函数为：，那么其对应的母函数为：从从x4的系数可知，从这的系数可知，从这8个元素中取个元素中取4个组合，不同个组合，不同的组合数为的组合数为10。这这10个组合可从下面的展开式中得到：个组合可从下面的展开式中得到： ()()()xxxxxxxx

35、 2322311122333111其中其中4次方项表示了一切从次方项表示了一切从8个元素中取个元素中取4个的组合个的组合方案。方案。例如例如 表示一个表示一个a1三个三个a3的组合，的组合， 表示两个表示两个a1两个两个a3的组合，依此类推。的组合，依此类推。331xx2321xx()( )( )( )xxxxx xxx xx xxxx xx xx xx x xx xx xx xxx xx xx xx x xx xx xx x xx x xx xx x221231122133322223311212131232223332223132331323132223223123231312312313

36、221211接下来讨论从这接下来讨论从这8个元素中取个元素中取4个的不同陈列总数。个的不同陈列总数。以两个以两个a1两个两个a3组合为例，不同陈列数为组合为例，不同陈列数为4!/(2!2!)。同样一个同样一个a1三个三个a3的不同陈列数为的不同陈列数为4!/(1!3!)。依此类推可以得到不同的陈列总数为：依此类推可以得到不同的陈列总数为：! ! ! ! ! ! ! ! ! ! ! ! ! ! 1111111 31 32 21 1 22 23 1411112 1 11 2 13 12 2. 16183670( )()()()!exxxxxxxxGx 2322311112312123为了便于计算，

37、利用上述特点，方式地引进函数为了便于计算，利用上述特点，方式地引进函数xxxxxxxx 23456789143517358113231212727272! .!xxxxxxxx 2345678392870112341703505605605678从右边很容易可以看出，取从右边很容易可以看出，取2个的陈列数为个的陈列数为9，取，取3个个的陈列数为的陈列数为28，取，取4个的陈列数为个的陈列数为70依此类推。依此类推。定义：对于序列定义：对于序列a0,a1,a2,，函数，函数( ) !kkeaaaaGxaxxxxk 233120123称为序列称为序列a0,a1,a2,对应的指数型母函数。对应的指数

38、型母函数。这样，对于一个多重集，其中这样，对于一个多重集，其中a1反复反复n1次，次，a2 反反复复n2次，次，ak反复反复nk次，从中取次，从中取r个陈列的不同个陈列的不同陈列数所对应的指数型母函数为：陈列数所对应的指数型母函数为：( ) ! .!knennkxxxGxnxxxxxxnn1221222112111212例例18 求以下数列的指数型母函数：求以下数列的指数型母函数：( )(, );( );( ).nnnnaP m naab 1213( )( )(, )(, )() .!nmnmennxGxP m nC m n xxn 0011( )( ).!nnbxenxGxben 03( )( ).!nxenxGxen 021例例19 由由1，2，3，4四个数字组成的五位数中，要求四个数字组成的五位数中，要求数数1出现次数不超越出现次数不超越2次，但不能不出现；次，但不能不出现； 2出现次出现次数不超越数不超越1次；次； 3出现次数最多出现次数最多3次，可以不出现；次，可以不出现；