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

1、考保丈I教案课程名称：组合数学授课教师卢奕南所在单位计算机科学 与技术学院课程类型讲授授课时间32学时授课对象本科生三年级教学内容提要时 问 分 配 及 备 注在第二章中，已解决了部分排列组合问题。但对于不尽相异兀素的部分排列和组合，用第二章的方法是比较麻烦的，若改用生成函数方法，问题将显得容易多了。其次，在求解递推关系的解、整数分拆以及证明组合恒等式时， 生成函数是一种非常重要的手段。 本章通 过例题的解答，显示了生成函数方法确实是组合数学中的基本而重要的方法，它是连接离散数学与连续数学的桥梁， 而且组合数学中的问题能借助于生成函数的方法、原理，获得统一的处理和解决方式生成函数(母函数) 。

2、生成函数方法的基本思想是把离散的数列向多项式或哥级数对应起来，从而把离散数列间的结合关系转换为多项式或哥级数之间的运算。本节主要讨论几类特殊的生成函数，即组合数序列、排列数序列、分拆数序列、组合分配数序列以及排列分配数序列的生成函数，以及Catalan数和A类Stirling数的生成函数。5.1 生成函数的定义与性质5.1.1 生成函数的定义定义5.1.1设一个有限或无限数列00 > a11 a2 ) t做形式哥级数A(x) =a0 +a1x + a2x2 + anxn + ,称A (x)为序列a0,a1,a2，的生成函数，并记为 Ganl3学 时例5.1.1组合数序列C(n,r) ,

3、r = 0,1,2，n的生成函数是fn(X)=(1 X)n.通过对(1 +x)n的运算，可能导出一系列组合数的关系式，例如:n“ ii z0二 n 2nJ= 2n,由恒等式(1 x)m n =(1x)m(1x)n可以推导出Vandermonde恒等式rk zQ<kk例5.1.2无限数列1,1，的生成函数是12 n1 x x x1 -x例 5.1.3 求数列a1，a2,an,的生成函数其中an是多重集8，b1严b2,严灯的n组合数'k +n 1、的生成函数。解该数列记作an,它的生成函数是gk(x)=x+ d1,k + n1 xn 1 (1-x)= (1-x(5.1.1)当k=1时

4、，这时数列为例5.1.2的无限数列1,1，,其生成函数为_1_o1 - x当k=2时，3 电严b2的组合数是 n+1,这时数列变成1,2,，n+1,，而由(5.1.1 )式有12g(x)2 =1 2x 3x(1 -x)+(n +1)xn + 。例5.1.4投掷一次骰子，出现点数, 1 _1, 2,，6的概率均为1,问连续投掷两次，出现6的点数之和为10的概率有多少？解一次投掷出现的点数有6种可能，连续两次投掷到的点数构成二元数组2(i, j '(1 Mi, j <6 ),共有6 =36种可能，由枚举法，两次出现的点数之和为10的有3种可31能；(4, 6), (5, 5), (6

5、, 4),所以概率为=36 12如果问题是连续投掷 10次，其点数之和为30的概率有多少，这时就不那么简单了， 这 是由于10个数之和为30的可能组合方式很多， 难以一一列举，要解决这个问题，只能另辟 新径。我们用多项式23456x x x x x x表示投掷一次可能出现点数1, 2,，6,观察2345623456( 2345623456 x x x x x x )(x x x x x x ).从两个括号中分别取出xm和xn,使m n 10x x = x即是两次投掷分别出现点数m,n,且m + n=10,由此得出，展开式中x10的系数就是满足条件的方法数。同理，连续投掷10次，其和为30的方法

6、数为23456 10(x x x x x x )中x30的系数，而/23456、10(x x x x x x )1061010=x (1 -x ) (1 -x)10二 x10'(-1)ii =000Ei =010-1 +i ) ixi U J所以，x30的系数为29、皿,230 ； +170 ；11,10 ；141 1 乂8人2厂12人3 j=2930455.故所求概率为2930455610:0.0485.5.1.2生成函数的性质生成函数与数列之间是一一对应的，因此，若两个生成函数之间存在某种关系，那么相 应的两个数列之间也必然存在一定的关系；反之亦然。00设数列Qo,ai,a2,的生

7、成函数为 A(x)=£ akXk ,数列由0,。由2广的生成函数为k 0Q0 kB(x) =Z bkX ,我们可以得到生成函数的如下一些性质：k O性质1若0 (k :二 r)bk = «aj(k 之 r)则_rlB(x) =x A(x).证明由假设条件，有aaB(x) =Z bkxk =b0 +b1x1 +b2x2 + +br_1xr_1 +brxr +br41xr* +"k =0CO二、，bkxk =0 00 brxr br1xr 1k 土rcd一krr 1.= a/ 二a°xaxk 比r=x A(x).性质2若bk=ak+,则17kB(x) = r

8、 (A(x) -y akx ).xk=0证明类似于性质1的证明。k性质3若bk = £ ai ,则i =0B(x) = A(x).1 -xkk证明 给等式bk =Z ai的两病都乘以x ,得i -0bo = a0,bix = a°x ax, ,22222x = a0xa1xa2x , kkkkkbkx = a0xa1xa2x -，akx ,.把以上各式的两边分别相加，得 2、2、2 , .2、B(x) = a0(1 x x ) a1x(1 x x ) a2x (1 x x ),2、-2、二(a。aix a2x)(1 x x )_ A(x) .1 - xod性质4若bk =

9、£ ai ,则 i水B(x)J(x).1 - xcd这里，工ai是收敛的。 i =0odod证明 因为A(1) =£ ak收敛，所以bk =£ ai是存在的，于是有k =0i *b0 = a0 , a , a2 . 二 A(1),b1x =ax a2x =A(1) -a0x, .2222b2x =a2xa3x= A(1) - a0 - a1 x , kkkkbkx =akx a - x = A(1) - a0 - a1 -akx,.把以上各式的两边分别相加，得十)-2kB(x) = A(1) A(1) -a0x A(1)-a0 -ax A(1)-a0-a-x=A(

10、1)(1 x x2) -a0x(1 x x2' ) - an4xn(1 x x2二A(1) -x(a0a1x a2x2) (1 x x2)_ A(1) -xA(x) .1 -x性质5若bk = kak,则B(x) = xA (x).证明由A'(x)的定义知008xA(x) =x“ kakXkJ =、' kakXkk4k -0oO k二bkx = B(x).k 乂性质6若bk =国二，则k 11 x B(x) A(t)dt.x 0证明由假设条件，有x： - x k0 A(t)dtc 0aktkdtk =0八一卜(k 1)tkdtk z0oO k : ri ="b

11、kxk =0=x B(x).性质7若Ck =«ak + Pbk,则QOC(x)三ckxk =1 A(x) 6(x).k -0性质 8 若Ck =a0bk +aibk+akb°,则oO kC(x)三ckx = A(x) B(x).k 0性质9若b="nan,豆为常数，则B(x)=A(sx)。性质7和性质8可以形式哥级数的数乘、加法及乘法运算的定义直接得出。卜面列出几个常利用这些性质，我们可以某些数列的生成函数，也可以计算数列的和。见的简单数列的生成函数，其中 k =0,1,2，：1(1) G1 =;1 一x(2) g'J-；1 -ax(3)x(1 -x)2(

12、4)G氏(k *) = /=； (1 -x)(5)Gk2，"；(6) GH(k 1)(k 2) ： ：6x 4； (1 - x)4G= ex;k! 1(8)Ct klr(1 x)a;(9)'n +k(1-x)n1,G1k卜面证明其中的几个：证明 (3)aOodQOG'k.=，kxk = x' kxk1 x x(v xk)k=1k 1k =0/ 1 x=x()2 .1 -x (1 -x)(5)G42k2xkk 18oQ=% (k 1)kxk，kxkk 1k 12x x(1-x)3 -(1-x)2_ x(1 x)3(1-x)(6)设Gl(k 1)(k 2) ； =

13、 A(x),x8 xkgtA(t)dt=£ gk(k+1)(k+2)tdtk 4oo=Z k(k +1)xk”kU2 2x =x3 .(1-x)所以'2x3"xA(x) = 36x)l6x2"(1-x)4,故A(x)= j(1 -x)4例5.2.1求Qn 的生成函数0,n =0,1,2,a : an1 (-1)n,n>3.例5.1.4已知%n的生成函数为一、2+3x-6x2A( x)=,1 -2x求an ,解用部分分式的方法得 一 .一一 2 /、2+3x-6x2A(x)=1-2x-2+3x,1 -2x而2 0，n n-2Z 2 x1 -2xn=eo

14、O k n + n=2 2 x ,n =0所以有2n41(n#1)_2-2 +3 = 7 (n =1).例5.1.5计算级数2 _2212 n的和。解 由前面列出的第(5)个数列的生成函数知，数列。号的生成函数为此处,由性质 / 'x(1 x) ; kA(x)3 -akx ,。- x) k/2 人 ak =k .令2_ 22bn =12 n ,3即得数列机的生成函数为oOB(x) = " bnxnn =0A(x)1 - xx(1 x)(1 -x)4oO=(x x2)二k=0'fk 也 J比较等式两边xn的系数，便得1222n2三4'n +2_ n(n 1)(2

15、n 1).65.2组合数的生成函数我们在前面几章中讨论过三种不同类型的组合问题:(1) 求。1色，an的k组合数;(2) 求& 1产®2,尸a ）的k组合数;(3) 求13 ,4 a ,5a的10组合数。其中，问题（1）是普通集合的组合问题；问题（2）转化为不定方程 x1 x2 +xn =k的非负整数解的个数问题；问题（3）是第四章的例子，利用容斥原理来计数。它们在解题方法上各不相同。下面我们将看到，引入生成函数的概念后，上述三类组合问题可以统一地处理。定理3.3.1 设多重集S =r1e ,i2e2,im-6m,且i1+ i2+im= n，则 S 的 k可重组合数Ck对应序

16、列Ck的生成函数为riG(x) =n G xj i"g )k其中，k可重组合数Ck为G（x）展开式中x的系数。证明 令G（x）中各 工 的项分别对应诸元素的某种可能取法。例如，对i = t, xr表示元素et选取了 r次。依次类推。显见G（x）展开式中的项xk具有一般形式kk1k2 .kmx = x x x其中kik2km =k, 0Mki 3, i =1,2, ,m对此方程的一非负整数解（&*2，km）（在前提0Eki Wji =1,2,m下），乘积xk1,xk2 L .xkm就对应了诸元素 e，62,，6m的一种可重取法。合并同类项后,xk的系数就表示了多重集S中取出k个

17、元素的所有可能的可重组合数ck 0推论5.2.1 设S =g e1产.62,严em,若限定元素6i出现的次数集合为r（1 <i <n）,则从S中取出k个元素的组合数Ck对应序列a的生成函数为我们先从问题（2）开始，令M =笛a严 a,产an的k组合数为bk , n个形式哥级数的乘积就是序列 bk的生成函数:222、(1 x x )(1 x x ) (1 x x )=(1 xx2)n二,(1 -x)从而中xk的系数就是 M的k组合数bk ,因此为bk =n -1 kk这时，我们再次得到了第 获得的。3章中多重集合 M的k组合数的公式，只不过现在是用生成函数用生成函数方法解问题(3)尤

18、为简单，将3 a,4 b,，5 c的k组合数记为bk , bk的生成函数就是2(1 x x32342345、x )(1 x x x x )(1 x x x x x )=(1 - x4) (1 x5).(1x6) 1(1 -x)4569101115、= (1-x - x - x x x x - x )cd王n=0"2'xn,所以，x10的系数bio为b10'10+2)命+2)'5 + 2、/4 + 2)1+2)/0 + 2)十0I4与第4章中用容斥原理得到的结果相同。在普通集合ai，a2,，an的k组合中，ai(1 <i W n)或者出现或者不出现，故该集

19、合的k组合数序列 bk的生成函数为n xk, 口n(1 x)n -k=0从而例5.2.1设5=8向产%,产-em,则S的每个元素至少取一次的k (无限)可重 组合数ck(k之m)对应序列ck的生成函数为J 00 G(x) = E xj ；jmXm(1 -X)G(x) =xm'k 0QO k x =2 k=0m4kx00=£k=0” 1kIkmJ其组合数Ck为G(x)展开式中xk的系数C(k -1,m-1) o这是由于例5.2.2求不定方程ki +k2+k3 +k4 =20的解组数。其中，限制 ki可取0, 2, 4; k2可取1, 3, 5; k3可取6, 7; k4可取8,

20、 9。 m解 设不定方程£ X = k的解组数目为ck ,本例中m = 4,k = 20。注意到对 i 1ki(i =1,2,3,4)的限制，序列cj对应的生成函数为20c e1q04356789G(x) =(1 x x )(x x x )(x x )(x x )由G(x)展开式中x20的系数知题给不定方程解组数目为C20 =6。例5.2.3设有5个红土和8个黄球，要求每次取出不少于2个红球和偶数个黄球，求所有的组合方式数。解组合方式数对应序列的生成函数为23452468G(x) = (xxxx )(1xxx x )345678910II12=xx2x2x2x2x 2x 2x2x 2

21、x 2x 2x13因此，总的组合方式数为 1 + 1+2X8+1+1=20。例5.2.4设有红球2个，黑、白球各1个，问(1)共有多少不同的选取方法？试加以枚举。(2)若每次从中任取 3个，有多少种不同取法？012.、解(1)设用r,b,切分别代表红、黑、白三种球，两个红球的取法与r ,r ,r对应，即红球的可能取法与1+r+r2中r的各次哥对应，亦即 r°=1表示不取红球，r1表示取1个红球，r2表示取2个红球。对其它球，依此类推法，则不同选取方法数所形成序列对应的生成函数为G(r,b, ) =(1 r r2)(1 b)(1)=1 (r b ) (r2 rb r b ) (r2b

22、r2 , rb ) r2b ,分析上式，不难发现1： 一个球都不取，仅有一种方案；r +b+。：取1个球的方案有3种，分别为红，黑，白；r2 +rb +ro +bo :取2个球的方案有4种，分别为红红，红黑，红白，黑白；r2b +r2be+山0：取3个球的方案有3种，即2红1黑，2红1白，三色球各取其一;r2b© :取4个球的方案仅1种，即所有球全取。若令r = b =1,即可求得所有不同的选取方案总数为G (1, 1, 1) =1 + 3 + 4 + 3 + 1 = 12(2)若只考虑每次取 3个球的方案数，而不需枚举，则可令 r = b = 6 = X。写出G(x) =(1 x

23、x2)(1 x)2 =1 3x 4x2 3x3 x4由x3的系数知所求方案为 3种。例5.2.5 求不定方程x1+2x2=15的非负整数解的个数 a15。11-y2解 设a的生成函数为 A (y),则1A( y) =(1 y y2)(1y2y ),1 - y1 二r 1 二wjr+1)y+/y111!+!+! 2(1 -y)24(1 -y) 4(1 y)1 11ran =-(r +1) +- +-(-1)。2 4 4例5.2.6从n双互不相同的鞋子中取出r只(r<=n),要求其中没有任何两只是成对出现的，问有多少种不同的取法？解(一)：令S =12 e,2 e2,，20),但同类中的两个

24、 e是不同的，故其r重组合的生成函数为： n(1 2x)n = " C(n,r)2r xrr =0即不同的取法为 C(n,r 2r解(二)：用排列组合法。先从 n双鞋中选取r双，共有C(n,r), 再从此r双中每双取出一只，由乘法原理，即得。C(n,r )x 2X2 X2 =C(n,r2r解(三)：先取出k只左脚的鞋，再在其余 n-k双鞋中取出r-k只右脚的鞋，用乘法原理得C(n,k)C(n -k,r -k)(k =0,1，r),则总的取法为：-r -C(n,0)C(n -0,r) C(n -1, r -1) C(n,2)(n -2,r -2) C(n,r)C(n -r,r - r)

25、 =2 C(n,r)5.3排列数的指数型生成函数当涉及到与排列有关的问题时，通常使用指数型生成函数。例如 n元集合的k排列数为n(n 1)(n -k +1),按5.5.1小节中方法构成的生成函数为：COn(n -1) (n -k 1)xkk =0没有简单的解析表达式，但如果把基底函数k kXX改换成一，则 k!一二xkn(n -1) (n - k 1)k卫k!=(1 + x)n。这启发人们引入指数型生成函数的概念。数列a0,ai,a2,的指数型生成函数定义为形式哥级数二-xkkk k!定理5.3.1若元素e1可重复a1,a2,次，元素e2可重复 可，口2， 次，元素em可重复儿十九2,次，则m

26、元集的这种k可重排列数Pk对应序列Pk的生成函数为G(x)='、kk « fa笛心九、Pk S=£ !S 9 Fz I !k! I 1%!又、Pi! J i I%! J事实上，上式右端等于xkk!由多项式系数的组合学意义知，k!/(ai1! + Pi2! + “ +九im!)正是元素s出现弭次，元素G出现Pi2次，元素em出现及m次的k可重排列数。故按所有可能的 (a% +Pi2 +%m =k)求和，即得总的k排列数Pko推论5.3.1设5=修 0严%,严 .,若元素ei(i =1,2,，m)重复出现的次数构成集合，则集S中元素的这种k可重排列数Pk对应序列 Pk的

27、生成函数为m、. xjG(x)'T j m j!k可重排列数Pk为G(x)展开式中xk/k!的系数。推论5.3.2设m元多重集S =r1e,r2e2，rmem,且r1+r2+rm= n ,则iJ=0 j!xj的k可重排列数 Pk对应序列 Pk的指数型生成函数为mGe(X)刊.1i 4其中，k可重排列数Pk为Ge(x)展开式中xk/k!系数(k = 0,1,2,)。n特别地，数列1,1，的指数型生成函数 e(x)=£ 二具有与指数函数相似的性质: n=o n!e(x)e(y) =e(x y).这是因为从而xi&x)e(y) 5 i!二 yj j j!1x i z0 i!

28、oO=£n 000=£n=0od=£n=0oO z k=0ky I x k!(n-k)!<x j /、n n一 x I x1 + J 1 y J n!(x y)nn!二 e(x y).e(x) e( -x) =e(0) = 1,e( -x)=e(x)数为5.3.1多重集合M =0°切产a2, 产an的k排列数序列bk的指数型生成函2x x1 1rx +一上.-1!2!e en (x)= e(nx)二二 k k x二 nk $ k!从而bk =nk.例5.3.2 3个红球，2个黄球，3个蓝球，每次从中取出4个排成一旬，求排列方案数。解 m=3,1 =

29、3,2 = 2,口 =3,k=4 由推论Ge(X)=21 XX_1!2!3!人9 2143=1 3x x x 232 XX=1 3928X X/xX1- X +3!1!2!A1!2!354175 3565X:卜X XX12127272345XXX-70170 3505.4.2 知24!5!1231!2!3!78XX3505607!8!718X726 X6!故知，从所给例 5.3.32最多出现1n色球取出4个的排列方案有70种。由1, 2, 3, 4能组成多少个五位数？要求这些五位数中1出现2次或3次,次，4出现偶数次。解根据题意，有M1M2M3=2,3, =0,1, = 0,1,2, ,M4

30、=0,2,4, .由推论5.4.2知，该排列数的指数型生成函数为2, X X .1 - -2!3! .1!1!2!4 X + 4!5所以的系数为5!2X2=6 (3 4x X2) e(X)2e(x) e(-x)X2= 12(3 4x X2)(e(2X)1),5辞工 13M 2-+4父2- +俨彼=140, 12、3!2!1!即满足题意的五位数有 140个。例5.3.4 求M =°°3产a?,产an的k排列中每个ai（1i Wn）至少出现一次的排列数Ak的指数型生成函数。解根据题意，有Mi =1,2,3(1<i <n).由推论5.3.2知，排列数序AJ的指数型生成

31、函数为23xxx_ + 一 + 一 +1 1!2!3二 (e(x)-1)nn八(-1),i =0zn '、,e(n-i)x)nC (-1)ii =0n 看(n i)kxk<i 0 k!i n ；二£ 工(-1)i . !(n-i)km=0lik xk!A=£ (-1)i n (n-i)k(k>n).li所以i=0满足本题条件的排列a. a. a.i1 i2ik可以看成是把k个不同的球1, 2,，k放入n个不的盒子a1,a2，an,并且每盒非空的 一种放法，即球j放入盒子a,中(1 W j Wk),在第2章2.7节中我们知道共有Ak =n!S(k,n)种放

32、法，由此得出k元集合的n分划数的显式表达式1 二/n',S(k,n)=-Z (-1)i , (n-i)k.n!f(i )由此可知，S(k, n)的指数型生成函数为1n(e(x) -1).n!5.4 Catalan数列与Stirling数列的生成函数本节介绍Catalan数列和Stirling数列这两种数列的生成函数。5.4.1 Catalan数列的生成函数Catalan数首先是由Euler在精确计算对凸 n边形的不同的对角三角形剖分的个数问题 时得到的，它经常出现在组合计数问题中。例5.5.1在一个凸n边形中，可以用n-3条不在内部相交的对角线将其分成n-2个三角形，问有多少种不同的分

33、法？令h(n)表示分一个n + 1条边的凸多边形为三角形的方法数，并规定h(1)=1。当n = 2时，n + 1边形就是三角形，不需要用对角线进行三角形剖分，故 h(2) = 1。当n之3,考虑一个凸n + 1边形，它的顶点分别用A1, A2,，An书表示，如图5.5.1所示。取定多边形的一条边AAn书，任取多边形的顶点 Ak书(k=1,2,，n-1),将Ak书分别与A,An书之间连线，得三角形T,三角形T将凸n + 1边形分成T , Ri和R2三部分，其中，Ri为k +1边形，R2为n k+1边形。因此，R可以用h(k)种方法划分，R2可以用h(n-k) 种方法划分，所以n -1h(n) =

34、£ h(k)h(nk).(5.5.1)kW这正是Catalan数列的形式。Ak+1图 5.5.1例5.4.2 求n个数a1，a2,，an的乘积P = a1a2an共有多少种不同其中，乘法不满足结合律，不改变名数的顺序，只用括号表示成对的乘积, 的乘法方案？解 设对n个数的乘积有f(n)种方式。在a1,a2，an的每个格式中，存在着最后的 乘法(对应外层的圆括号)(a，a2,，ak的格式)父(ak书，an的格式)关于ai,a2,，ak的乘法格式可以有 f(k)种方式选择，而 ak柏，an的乘法格式有 f(nk)种方式选择，对k取1,2，n1中的任一个，因此有n 1f(n)八 f(k)f

35、(n-k),'kmJ(1)=1.则它与Catalan数满足同一个递推关系。例题3.4.1从(0, 0)点到(n , n)点的除端点外不接触直线 y = x的路径数为2 2、 l=2h(n),其中，h(n)为 Catalan 数。n n -1 J那么如何求h(n),本节用n的生成函数G(x)来计算。QOG x 二 hxh2x2hi xii 1oO oOcO coG2 x =" hix'hixi - " h' hihj xi ji 1 i 1i m j mx x xn% hihn-L =、hnxnn =2cO二、hnxn - x = G x - xn丑解 G2(x )G(x )+x =0 ,得利用牛顿二项式定理，有6.1 -4x =1 八1(1 J f 1-1、in +1 2 <2J 12) /、n：(-4) xn!n 11 一."_4x因为ho =0,开方应该取负号，故舍去 G(x)= 1 丫 1 4x ,得Gx =1 -，1 -4x 1n 1C2n 2x