5.4-Catalan数列与Stirling数列的生成函数

教案课程名称：组合数学授课教师卢奕南所在单位计算机科学与技术学院课程类型讲授授课时间32学时授课对象本科生三年级教学内容提要时间分配及备注在第二章中，已解决了部分排列组合问题。但对于不尽相异元素的部分排列和组合，用第二章的方法是比较麻烦的，若改用生成函数方法，问题将显得容易多了。其次，在求解递推关系的解、整数分拆以及证明组合恒等式时，生成函数是一种非常重要的手段。本章通过例题的解答，显示了生成函数方法确实是组合数学中的基本而重要的方法，它是连接离散数学与连续数学的桥梁，而且组合数学中的问题能借助于生成函数的方法、原理，获得统一的处理和解决方式生成函数（母函数）。生成函数方法的基本思想是把离散的数列同多项式或幂级数一一对应起来，从而把离散数列间的结合关系转换为多项式或幂级数之间的运算。本节主要讨论几类特殊的生成函数，即组合数序列、排列数序列、分拆数序列、组合分配数序列以及排列分配数序列的生成函数，以及Catalan数和第一类Stirling数的生成函数。5.1生成函数的定义与性质5.1.1生成函数的定义定义5.1.1设于一个有限或无限数列,,,,210aaa做形式幂级数nnxaxaxaaxA2210)(，称A（x）为序列,,,210aaa的生成函数，并记为.naG3学时例5.1.1组合数序列),(rnC，nr,,2,1,0的生成函数是.)1()(nnxxf通过对nx)1(的运算，可能导出一系列组合数的关系式，例如：ninin0,2.,201ninnini由恒等式nmnmxxx)1()1()1(可以推导出Vandermonde恒等式.0rkkrnkmrnm例5.1.2无限数列},,1,1{的生成函数是nxxxx2111例5.1.3求数列,,,,21naaa的生成函数，其中na是多重集},,,{21kbbb的n组合数nnk1的生成函数。解该数列记作na，它的生成函数是)(xgk，则kknkxxxnnkxkkxg)1()1(11101)(（5.1.1）当1k时，这时数列为例5.1.2的无限数列},,1,1{，其生成函数为x11。当2k时，},{21bb的组合数是1n，这时数列变成,1,,2,1n，而由（5.1.1）式有nxnxxxxg)1(321)1(1)(22。例5.1.4投掷一次骰子，出现点数1，2，…，6的概率均为61，问连续投掷两次，出现的点数之和为10的概率有多少？解一次投掷出现的点数有6种可能，连续两次投掷到的点数构成二元数组6,1,jiji，共有3662种可能，由枚举法，两次出现的点数之和为10的有3种可能；（4，6），（5，5），（6，4），所以概率为.121363如果问题是连续投掷10次，其点数之和为30的概率有多少，这时就不那么简单了，这是由于10个数之和为30的可能组合方式很多，难以一一列举，要解决这个问题，只能另辟新径。我们用多项式65432xxxxxx表示投掷一次可能出现点数1，2，…，6，观察).)((6543265432xxxxxxxxxxxx从两个括号中分别取出mx和nx，使,10xxxnm即是两次投掷分别出现点数nm,，且10nm，由此得出，展开式中10x的系数就是满足条件的方法数。同理，连续投掷10次，其和为30的方法数为1065432)(xxxxxx中30x的系数，而01006101010610106543211010)1()1()1()(iiiiixiixixxxxxxxxxx所以，30x的系数为.293045531021121081711014232029故所求概率为.0485.062930455105.1.2生成函数的性质生成函数与数列之间是一一对应的，因此，若两个生成函数之间存在某种关系，那么相应的两个数列之间也必然存在一定的关系；反之亦然。设数列,,,210aaa的生成函数为0)(kkkxaxA，数列,,,210bbb的生成函数为0)(kkkxbxB，我们可以得到生成函数的如下一些性质：性质1若)()(0rkarkbrkk则).()(xAxxBrl证明由假设条件，有lkrrklkrrrrrlkkkkrrrrrrkkxaxaxaxbxbxbxbxbxbxbxbbxbxB110110111122110000)().(xAxr性质2若,rkkab则).)((1)(10rkkkrxaxAxxB证明类似于性质1的证明。性质3若kiikab0，则.1)()(xxAxB证明给等式kiikab0的两端都乘以kx，得.,,,,,2102221202210100kkkkkkkxaxaxaxaxbxaxaxaxbxaxaxbab把以上各式的两边分别相加，得.1)()1)(()1()1()1()(222102222120xxAxxxaxaaxxxaxxxaxxaxB性质4若kiikab，则.1)()1()(xxxAAxB这里，0iia是收敛的。证明因为0)1(kkaA收敛，所以kiikab是存在的，于是有.,])1([,,])1([,])1([),1(110121023222202112100kkkkkkkkxaaaAxaxaxbxaaAxaxaxbxaAxaxaxbAaaab把以上各式的两边分别相加，得.1)()1()1()]()1([)1()1()1)(1(])1([])1([])1([)1()(2221021202102100xxxAAxxxaxaaxAxxxaxxxaxxAxaaAxaaAxaAAxBnnkk性质5若kkkab，则).()(xAxxB证明由)(xA的定义知).()(0011xBxbxkaxkaxxAxkkkkkkkkk性质6若1kabkk，则xdttAxxB0.)(1)(证明由假设条件，有).()1()(0100000xBxxbdttkbdttadttAkkkkxkkkxkkx性质7若kkkbac，则0).()()(kkkxBxAxcxC性质8若0110bababackkkk，则0).()()(kkkxBxAxcxC性质9若nnab，为常数，则)()(xAxB。性质7和性质8可以形式幂级数的数乘、加法及乘法运算的定义直接得出。利用这些性质，我们可以某些数列的生成函数，也可以计算数列的和。下面列出几个常见的简单数列的生成函数，其中,2,1,0k：（1）;111xG（2）;11axaGk（3）;)1(2xxkG（4）;)1(2)1(3xxkkG（5）;)1()1(32xxxkG（6）;)1(6)2)(1(4xxkkkG（7）;!1xekG（8）;)1(axkG（9）.)1(11nxkknG下面证明其中的几个：证明（3）.)1()11()(20111xxxxxxkxxkxkGkkkkkk（5）32311122)1()1()1()1(2)1(xxxxxxxkxkxkxkkGkkkkkk（6）设),()2)(1(xAkkkG则.)1(2)1()2)(1()(32120101xxxxkkdttkkkdtttAkkxkxk所以,)1(6)1(2)(4233xxxxxxA故.)1(6)(4xxxA例5.2.1求na的生成函数例5.1.4已知na的生成函数为,21632)(2xxxxA求na，解用部分分式的方法得,321221632)(2xxxxxxA而,222212010nnnnnnxxx,2,1,0,0.3,)1(nnnna所以有).1(732)1(221nnn例5.1.5计算级数22221n的和。解由前面列出的第（5）个数列的生成函数知，数列2n的生成函数为,)1()1()(03kkkxaxxxxA此处，.2kak令,21222nbn则nkknab1,由性质3即得数列nb的生成函数为.3)()1()1(1)()(0240kknnnxkkxxxxxxxAxbxB比较等式两边nx的系数，便得211221222nnnnbnn.6)12)(1(nnn5.2组合数的生成函数我们在前面几章中讨论过三种不同类型的组合问题：（1）求naaa,,,21的k组合数；（2）求naaa,,,21的k组合数；（3）求naaa5,4,321的10组合数。其中，问题（1）是普通集合的组合问题；问题（2）转化为不定方程kxxxn21的非负整数解的个数问题；问题（3）是第四章的例子，利用容斥原理来计数。它们在解题方法上各不相同。下面我们将看到，引入生成函数的概念后，上述三类组合问题可以统一地处理。定理5.3.1设多重集},,{2211mmerererS，且nrrrm21，则S的k可重组合数kc对应序列}{kc的生成函数为mirjjixxG10)(其中，k可重组合数kc为)(xG展开式中kx的系数。证明令)(xG中各的项分别对应诸元素的某种可能取法。例如，对rxti,表示元素te选取了r次。依次类推。显见)(xG展开式中的项kx具有一般形式mkkkkxxxx21其中mirkkkkkiim,,2,1,0,21对此方程的一非负整数解),.,(21mkkk（在前提mirkii,,2,1,0下），乘积mkkkxxx21就对应了诸元素meee,,,21的一种可重取法。合并同类项后，kx的系数就表示了多重集S中取出k个元素的所有可能的可重组合数kc。推论5.2.1设},,,{21meeeS，若限定元素ie出现的次数集合为)1(niPi，则从S中取出k个元素的组合数kc对应序列}{kc的生成函数为miPjjixxG1)()(我们先从问题（2）开始，令},,,{21naaaM的k组合数为kb，n个形式幂级数的乘积就是序列{kb}的生成函数：)1()1)(1(222xxxxxx=,)1(1)1(2nnxxx从而中kx的系数就是M的k组合数kb，因此为.1kknbk这时