组合数学课件第七章生成函数

1、目录（目录（1）第第1章章 什么是组合数学什么是组合数学1.1引例引例1.2组合数学研究对象、内容和方法组合数学研究对象、内容和方法第第2章章 鸽巢原理鸽巢原理2.1 鸽巢原理：简单形式鸽巢原理：简单形式2.2 鸽巢原理：加强形式鸽巢原理：加强形式2.3 ramsey定理定理2.4 鸽巢原理与鸽巢原理与ramsey定理的应用定理的应用本章小结 习题第第3章章 排列与组合排列与组合3.1 两个基本的计数原理两个基本的计数原理3.2 集合的排列与组合集合的排列与组合3.3 多重集的排列与组合多重集的排列与组合本章小结 习题第四章第四章 二项式系数二项式系数4.1 二项式定理二项式定理4.2组合恒等

2、式组合恒等式4.3非降路径问题非降路径问题4.4牛顿二项式定理牛顿二项式定理4.5多项式定理多项式定理4.6 基本组合计数的应用基本组合计数的应用本章小结 习题第五章第五章 包含排斥原理包含排斥原理5.1 包含排斥原理包含排斥原理5.2 多重集的多重集的r-组合数组合数5.3错位排列错位排列5.4 有限制条件的排列问题有限制条件的排列问题5.5有禁区的排列问题有禁区的排列问题本章小结 习题目目 录录目录（目录（2） 第六章第六章 递推关系递推关系6.1 fibonacci数列6.2 常系数线性齐次递推关系的求解6.3 常系数线性非齐次递推关系的求解6.4 用迭代和归纳法求解递推关系本章小结 习

3、题第七章第七章 生成函数生成函数7.1生成函数的定义和性质7.2多重集的r-组合数7.3正整数的划分7.4指数生成函数与多重集的排列问题7.5 catalan数和stiring数本章小结 习题 第八章第八章 polya定理定理8.1置换群中的共轭类与轨道8.2 polya定理的特殊形式及其应用本章小结 习题*课程总结课程总结第第7章章 生成函数生成函数本章重点介绍本章重点介绍生成函数（生成函数、指数生成函生成函数（生成函数、指数生成函数）的基本概念及其在排列组合中的应用数）的基本概念及其在排列组合中的应用 ： 生成函数的基本概念生成函数的基本概念 生成函数的基本运算生成函数的基本运算 生成函数

4、在排列、组合中的应用生成函数在排列、组合中的应用 整数拆分整数拆分 生成函数在组合恒等式中的应用生成函数在组合恒等式中的应用第第7章章 生成函数生成函数 7.1生成函数的定义和性质生成函数的定义和性质 7.2多重集的多重集的r-组合数组合数 7.3正整数的划分正整数的划分 7.4指数生成函数与多重集的排列问题指数生成函数与多重集的排列问题 7.5catalan数和数和stiring第第7章章 生成函数生成函数7.1 生成函数概念4.1 生成函数的基本概念生成函数的基本概念定义定义 4.14.1.1 生成函数生成函数 注：注： f(x)是无穷级数，不管其收敛性；是无穷级数，不管其收敛性； x为形

5、式变元，为形式变元，f(x)为形式幂级数为形式幂级数 ； 序列与生成函数一一对应；序列与生成函数一一对应； 生成函数是序列的另一表达形式；生成函数是序列的另一表达形式； 有限序列也可用生成函数表示；有限序列也可用生成函数表示； 可与二项式定理结合应用可与二项式定理结合应用 。给定一无穷序列给定一无穷序列(a0,a1,an,)(简记为简记为an)，称函，称函数数 为序列为序列an的生成函数（发生、普的生成函数（发生、普通母函数）通母函数） 。 0( )iiif xa x7.1 生成函数例17.1 生成函数的基本概念生成函数的基本概念例例 题题7.1.1 生成函数生成函数 例例1、求序列求序列(c

6、(n,0),c(n,1),c(n,2), c(n,n)的生成函数。的生成函数。 解：解：由定义由定义7.1及二项式定理的推论有及二项式定理的推论有 ( ).01(1)nnnnnf xxxn x7.1 生成函数例27.1 生成函数的基本概念生成函数的基本概念例例 题题7.1.1 生成函数生成函数 例例2、求序列求序列(c(n-1,0), -c(n,1), c(n+1,2), , (-1)kc(n+k-1,k), )的生成函数。的生成函数。 解：解：由定义由定义7.1及二项式定理的推论及二项式定理的推论3.10.2有有 200111( ).( 1).0121( 1)(1)kkkkkknknnnnk

7、f xxxxknk =xkn =xxk 7.1 生成函数例34.1 生成函数的基本概念生成函数的基本概念例例 题题4.1.1 生成函数生成函数 例例3、证明证明(1-4x)-1/2是序列是序列(c(0,0), c(2,1), c(4,2), , c(2n,n),)的生成函数。的生成函数。 证明：证明：由牛顿二项式定理有由牛顿二项式定理有 由定义知，由定义知，(1-4x)-1/2是序列是序列(c(0,0), c(2,1), c(4,2), , c(2n,n),)的生成函数。的生成函数。1 211111 2(14 )1( 4 )1 21 211 22 .1 211( 4 )!41 3 . (21)

8、12!2! 1 3 . (21)1! !2 4 . (2 )1 3 . (21kkkkkkkkkkkxxkk +xkk +xkkkxk kkk 11121)! !(2 )!211! !0242.012kkkkkkkxk kkk xxkk kk xxxk 7.1 生成函数例47.1 生成函数的基本概念生成函数的基本概念例例 题题7.1.1 生成函数生成函数 例例4、求序列求序列(0, 123, 234, n(n+1)(n+2),)的生成函数。的生成函数。 nnnnnnnnnxxn nxxn nnxxxxn nnxxxxn nnxxf xx023234340211.10.412(1)(1)6(1)

9、(2)(1)6(1)(2)(1)01 2 32 3 4.(1)(2).6( )(1 由由牛牛顿顿二二项项式式定定理理的的推推论论，有有 将将上上式式两两端端同同时时微微分分两两次次得得 将将上上式式两两端端再再微微分分得得 两两边边同同乘乘解解以以 得得 因因此此 ：n nn4(0 1 2 3 2 3 4,., (1)(2),.) 是是序序列列 ，的的普普通通母母函函数数。7.1 指数生成函数概念7.1 生成函数的基本概念生成函数的基本概念定义定义 7.27.1.2 指数生成函数指数生成函数 注：注： fe(x)也是形式幂函数。也是形式幂函数。 经常可结合以下公式运算：经常可结合以下公式运算：

10、给定一无穷序列给定一无穷序列(a0,a1,an,)（简记为（简记为an），称函），称函数数 为序列为序列an的指数生成函数。的指数生成函数。 ieiixfxai0( )!nxnxxxen221.1!2! nxnxxxen21.( 1).1!2! nxxxxxeexn321sin.1!3!(21)!27.1 指数生成函数例57.1 生成函数的基本概念生成函数的基本概念例例 题题7.1.2 指数生成函数指数生成函数 例例5、设设n是整数，求序列是整数，求序列(p(n,0), p(n,1), p(n,n)的指数生成函数的指数生成函数fe(x)。 解：解：由定义由定义7.2及公式及公式p(n,r)=r

11、!c(n,r),以及例以及例1的的结论，有结论，有 nennxxfxp np np n nnnnn xxn x( )( ,0)( ,1).( , )1!.01(1)7.1 指数生成函数例67.1 生成函数的基本概念生成函数的基本概念例例 题题7.1.2 指数生成函数指数生成函数 例例6、求序列求序列(p(0,0), p(2,1), p(4,2), p(2n,n),)的指数生成函数的指数生成函数fe(x)。 解：解：由定义由定义7.2及公式及公式p(n,r)=r!c(n,r)，以及例，以及例3的结论，有的结论，有 nenxxxfxppppn nnn xxxn x221 2( )(0,0)(2,1

12、)(4,2).(2 , ).1!2!0242.012(14 )7.1 指数生成函数例77.1 生成函数的基本概念生成函数的基本概念例例 题题7.1.2 指数生成函数指数生成函数 例例7、求序列求序列1,2,n,的指数生成函的指数生成函数数fe(x)。其中。其中是实数。是实数。 解：解：由定义由定义7.2，有，有 特别地：若特别地：若 =1，则序列，则序列(1,1,1,)的指数生成函数为的指数生成函数为ex 。nnxexxxfxen22( )1.1!2! 7.1 指数生成函数例87.1 生成函数的基本概念生成函数的基本概念例例 题题7.1.2 指数生成函数指数生成函数 例例8、求序列求序列(1,

13、 14, 147, 147(3n+1),)的指数生成函数。的指数生成函数。 解：解：由定义由定义7.2和二项式定理，有和二项式定理，有 nennnnnnnnnxxxfxnnnxnnxnnxnxnx2011143( )1(14)(147).147. (31).1!2!147. (31)!3147.33313!4441.13331( 3 )!41( 3 )3(13 ) 7.1 生成函数定理17.1 生成函数的基本概念生成函数的基本概念定理定理 7.17.1.2 指数生成函数指数生成函数 设设f(x)、fe(x)分别为序列分别为序列an的普通、指数生的普通、指数生成函数，则成函数，则 xef xef

14、sx ds0( )()解：解：由指数生成函数的定义由指数生成函数的定义7.2，有，有 将上式两边同乘以将上式两边同乘以e-s并从并从0到到 积分得积分得由分部积分法有由分部积分法有故故0()()!nennsxfsxan00000()!nnnsssnennnns xxefsx dse adsae s dsnn0!sne s dsn00()( )snennefsx dsa xf x设设a(x), b(x), c(x)分别是序列分别是序列an, bn和和cn的生成的生成函数，则函数，则c(x)=a(x)+b(x)当且仅当当且仅当ci=ai+bi, (i=0,1,r,)c(x)=a(x)b(x)当且仅

15、当当且仅当 , (i=0,1,r,)7.2 生成函数运算定理27.2 生成函数的基本运算生成函数的基本运算定理定理 7.2iiki kkca b07.2 生成函数运算例17.2 生成函数的基本运算生成函数的基本运算例例 题题例例1、设设a(x)是序列是序列an的生成函数，则的生成函数，则a(x)/(1-x)是序列是序列a0,a0+a1,a0+a1 +an,的生成函数。的生成函数。nnnnxxxxxb xxcaacaaaacaaaaaaa xxa xb xa aaaa20001010101010010111.1-1 (1)(1,1,.,1,.)( )1 (1),111.11.1.( ) (1)(

16、 )( )(,.,. 由由牛牛顿顿二二项项式式定定理理知知故故是是序序列列的的普普通通母母函函数数。令令根根据据上上述述定定理理有有故故是是明明：序序列列证证na ,.)的的普普通通母母函函数数。7.2 生成函数运算例24.2 生成函数的基本运算生成函数的基本运算例例 题题例例2、求和求和 的值。的值。 rii2022210203203222231(0 ,1 ,.,.)(1-),1(1) 1(1) 1(0 ,1 ,.,.)(1)111iiiiiirrirxxxxxxixxxxxxi xxxxrxxcix先先求求序序列列的的普普通通母母函函数数。由由牛牛顿顿二二项项式式定定理理知知将将上上式式两

17、两端端对对 微微分分再再乘乘以以 得得（）再再将将上上式式两两端端对对 微微分分再再乘乘以以 得得（）故故（）是是序序列列的的普普通通母母函函数数。故故的的普普通通母母函函数数（）解解为为： 244400421114131.10 2(1-)(1)1(2)(1)(1) (1)(1)(21)213!3!6(1)(21)6iiiirrrixxxxxiixxxiixxxxrrrrr rr rrrrrrr rrci （） （）由由推推论论. . 知知故故的的展展开开式式中中的的系系数数为为（）故故7.2 生成函数运算推论17.2 生成函数的基本运算生成函数的基本运算六六个个推推论论推论推论7.2.1：0

18、( )( )lkk lklbb xx a xakl若若，则则0110111101111012012.0,.,.( ).00.0.(.)( )lllkk lllllllllllbbbba babab xbb xbxb xbxa xa xx aa xa xx a x证证明明：7.2 生成函数运算推论27.2 生成函数的基本运算生成函数的基本运算六六个个推推论论推论推论7.2.1：推论推论7.2.2：0( )( )lkk lklbb xx a xakl若若，则则10( )( )lklkk lkkbab xa xa xx若若，则则20122121212121012110( ).1.1( ).1( )l

19、lllllllllllllkklkb xbb xb xaaxaxa xaxaxxa xaa xa xaxxa xa xx证证明明：7.2 生成函数运算推论37.2 生成函数的基本运算生成函数的基本运算六六个个推推论论推论推论7.2.1：推论推论7.2.2：推论推论7.2.3：0( )( )lkk lklbb xx a xakl若若，则则10( )( )lklkk lkkbab xa xa xx若若，则则0( )( ) (1)kkiibab xa xx若若，则则见本节例见本节例1。7.2 生成函数运算推论47.2 生成函数的基本运算生成函数的基本运算六六个个推推论论推论推论7.2.4：0( )(

20、1)( ) (1)kkjkj kabab xaxa xx若若收收敛敛，则则20120012112022201( ). 1:.(1) : .(1) : .(1).( )(1)(1b xbb xb xbaaaax baaaaxbaaaab xax对对进进行行形形式式演演算算，有有 ： 证证明明22022122012.)(1.) (1.). =(1)(.) (1.) =(1)( ) (1)xa xxxa xxxax aa xa xxxaxa xx01( )( )1xkkabb xa x dxkx若若，则则7.2 生成函数运算推论5、67.2 生成函数的基本运算生成函数的基本运算六六个个推推论论推论推

21、论7.2.5：推论推论7.2.4：推论推论7.2.6：0( )(1)( ) (1)kkjkj kabab xaxa xx若若收收敛敛，则则( )( )kkbkab xxa x若若，则则设设a(x), b(x), c(x)分别是序列分别是序列an, bn和和cn的指的指数生成函数，则数生成函数，则c(x)=a(x)+b(x)当且仅当当且仅当ci=ai+bi, (i=0,1,r,)c(x)=a(x)b(x)当且仅当当且仅当 , (i=0,1,r,)7.2 生成函数定理37.2 生成函数的基本运算生成函数的基本运算定理定理 7.3 0iiki kkica bk6.5 母函数在递推关系中的应用6.5

22、母函数在递推关系中的应用母函数在递推关系中的应用 母函数法是求解递推关系的一种重要方法，不仅可母函数法是求解递推关系的一种重要方法，不仅可以求解常系数线性（非）齐次递推关系，也可以求解非以求解常系数线性（非）齐次递推关系，也可以求解非线性、非常系数的递推关系线性、非常系数的递推关系 。 求解的求解的方法和步骤方法和步骤为：为： 用用f(x)表示序列表示序列an的普通母函数；的普通母函数；利用递推关系利用递推关系an的表达式代入母函数的右端，或采用的表达式代入母函数的右端，或采用多项式形式算法，转化为关于多项式形式算法，转化为关于f(x)的方程的方程g(f(x)=0；1. 解出解出f(x)再展开

23、成幂级数，即可求得再展开成幂级数，即可求得an的初等表达式。的初等表达式。6.5 母函数的应用例1-16.5 母函数在递推关系中的应用母函数在递推关系中的应用例例 题题例例1、求递归关系求递归关系 nnnfffnff1201(2)1,1nnnnnnnnnnnnnnnnnnnnnnnf xf xf ffffff xf xff xffxff xxfxxfxff xxf xfxf xxf xx f xf x01012011221220112222010002( )(,.,.)( )( )()1( )( )1( )1 设设为为序序列列的的普普通通母母函函数数，并并将将式式代代入入有有解解之之得得解解：

24、xxx xxx221215151-0,22而而有有两两个个根根6.5 母函数的应用例1-26.5 母函数在递推关系中的应用母函数在递推关系中的应用例例 题题例例1、求递归关系求递归关系 nnnfffnff1201(2)1,12121212121211220011120111111211( )1(1)(1)1115(15),2 552 5555( )1155555151525nniinnninnnnnnabf xxxx xx xx xx xxxabxxf xx xx xxx xxx xxxxfxx故故用用待待定定系系数数法法解解之之得得故故（） （）6.5 母函数的应用例26.5 母函数在递推关

25、系中的应用母函数在递推关系中的应用例例 题题例例2、求递归关系求递归关系 112(1)(2)2nnaannannnnnnnnnnnnnnnnnnnf xa xa aaaanf xf xa xanxxxaxxnxxxxa xxxxf xxxxfnxxx1211112122122222102( )(,.,.)2(1)( )( )2(1)22(11)2222( )(1)22( )1(1)设设为为序序列列的的普普通通母母函函数数，并并将将式式代代入入有有解解之之得得解解： kkkkkknkknnkxxxxxknxxxnann32111200) 22 222 122 2 12222因因此此6.5 母函数

26、的应用例3-16.5 母函数在递推关系中的应用母函数在递推关系中的应用例例 题题例例3、求递归关系求递归关系 nnkn kkaaanaa1112(2)1,1nnnnnnnnnkn kknnnnkn knnnknnf xa xa aafxa xa xa aa axa axa axa xa xa x1122211223112211112121( )(,.,.)( ) . 这这是是一一个个非非线线性性的的递递推推解解：关关系系，设设为为序序列列的的普普通通母母函函数数，则则f xxxxfxfxfffxxf xfx12112( )114114( ),( )22(0)0(0)0( )114 ( )( )

27、2解解之之得得因因，而而，故故舍舍去去，有有6.5 母函数的应用例3-26.5 母函数在递推关系中的应用母函数在递推关系中的应用例例 题题例例3、求递归关系求递归关系 nnkn kkaaanaa1112(2)1,1注：注：通常，称满足上述递推关系的序列通常，称满足上述递推关系的序列(a1,a2,an,)为为catalan序列，称序列中的数序列，称序列中的数 为为catalan数。数。这个数很重要，它在各种不同的范围里经常出现，许多有意这个数很重要，它在各种不同的范围里经常出现，许多有意义的计数问题都与这个数有关。义的计数问题都与这个数有关。kkkknnnnnnnnnkzzzkkzxnxxnnn

28、xnnxnf xxnnnann1211121111( 1)22110 5 | |1,11124 ,( 1)22141( 4 )1222211114122 ( )12122 1 根根据据推推论论 .有有令令有有故故因因此此nnann12216.5 母函数的应用例4-16.5 母函数在递推关系中的应用母函数在递推关系中的应用例例 题题例例4、求递归关系求递归关系 nnnnanaa na a-1-201( -1)( -2)2(2)0,1nnnnnnnnnnnnnf xa xa aaf xfxna xxxfxna xaaxfxf xna xx xfxf x012111012( )(,.,.)( ) (

29、 ) ( )0,1 ( )( )(1) ( )( )这这是是一一个个非非常常系系数数的的线线性性齐齐次次递递推推关关系系，设设为为序序列列的的普普通通母母函函数数。将将微微分分有有将将上上式式两两端端同同乘乘以以 有有因因此此（注注意意初初值值条条件件）有有解解：nnnnnnnnnnnnnnnnnna xnaxx f xa xaxx xfxxxf xnanaax11222220222122(1)(2) 2( )22()( ) (12) ( )(1)(2)20 而而将将以以上上三三个个式式子子两两端端分分别别相相加加，并并由由递递推推关关系系得得6.5 母函数的应用例4-26.5 母函数在递推关

30、系中的应用母函数在递推关系中的应用例例 题题例例4、求递归关系求递归关系 nnnnanaa na a-1-201( -1)( -2)2(2)0,1xnnxnnnnnxnn innnnnnninxxfxxxf xxf xcexxxexnxnnxxf xcexcxnxcixnnia222200022000022()( )(12) ( )( )(1)( 2 )( 2)!(1)( )(1)( 2)( 2)!()! 故故有有解解此此微微分分方方程程得得而而，因因此此有有故故n inin inniciniacaini010( 2)()!11( 2)()!根根据据初初值值条条件件，可可得得，故故有有6.5

31、母函数的应用例5-16.5 母函数在递推关系中的应用母函数在递推关系中的应用例例 题题例例5、求求n位十进制正整数中出现偶数位十进制正整数中出现偶数个个5的数的个数。的数的个数。解解i：令令an=n位十进制数中出现偶数个位十进制数中出现偶数个5的数的个数的数的个数 bn=n位十进制数中出现奇数个位十进制数中出现奇数个5的数的个数的数的个数建立递推关系如下建立递推关系如下 这是关于序列这是关于序列an和和 bn的联立关系。的联立关系。设序列设序列an,bn的普通母函数分别为的普通母函数分别为a(x),b(x)。其中。其中nnnnnnaabbbaab111111998,1a xaa xa x b

32、xbb xb x a xa a x a x xa x a xa x xb x b x b x x a x221231232123212212( ).,( ).( ).9( )99.)( ).(19 ) (进进行行计计算算如如下下xb x x b xxa x)( )8(19 ) ( )( )1同同理理可可得得6.5 母函数的应用例5-26.5 母函数在递推关系中的应用母函数在递推关系中的应用例例 题题例例5、求求n位十进制正整数中出现偶数位十进制正整数中出现偶数个个5的数的个数。的数的个数。a xb xx a xxb xx b xxa xxxdxxxxxxa xxxxxxxxb xxxxxxa

33、xxx( )( )(19 ) ( )( )8(19 ) ( )( )119(18 )(1 10 )1917188( )119(18 )(1 10 )(18 )(1 10 )11198( )1(18 )(1 10 )(18 )(1 10 )179( )2 181 10故故可可得得关关于于普普通通母母函函数数和和联联立立方方程程组组nnnnnnnxa01(7 89 10 )21(7 89 10 )2 6.5 母函数的应用例5-36.5 母函数在递推关系中的应用母函数在递推关系中的应用例例 题题例例5、求求n位十进制正整数中出现偶数位十进制正整数中出现偶数个个5的数的个数。的数的个数。解解ii： n

34、-1位的十进制数的全体共位的十进制数的全体共 9 10n-2, 从中去掉含有偶数个从中去掉含有偶数个5的数，余下的便是的数，余下的便是n-1位中含有奇数个位中含有奇数个5的数。故有：的数。故有：nnnnnnbaaaaa xaa xa xxa xa xa xx a xaaxaax2112112123212221329 1089 108 ( ) . ) 8( ) 88. (18 ) ( )8(8)(8). (1 ，结结合合上上述述递递推推关关系系建建立立新新的的递递推推关关系系进进行行计计算算如如下下nnnnnnnxxx a xxxxxxa xxxxa2098718 ) ( )899 10.81

35、101 108711( )(7 89 10 )(18 )(1 10 )21 (7 89 10 )2 6.5 母函数的应用例66.5 母函数在递推关系中的应用母函数在递推关系中的应用例例 题题例例6、求递归关系（求递归关系（hanoi塔）塔） 1121(2)1nnaana解：解：设序列设序列an的普通母函数为的普通母函数为a xa xa xa xa xa xa xa xxa xa xa xx a xa xaaxaa23123231232312212132 ( ). ( ) . 2( ) 22. (1-2 ) ( )(2)(2)进进行行计计算算如如下下）nnnnna xxxxxx a xxxxxx

36、xxxa3230( )(12 )1. (1-2 ) ( ).111(21)(1)12 217.3 排列组合概述7.3 在排列组合中的应用在排列组合中的应用 生成函数有着极其广泛的应用，从本节开始介绍生生成函数有着极其广泛的应用，从本节开始介绍生成函数在某些组合数学的问题中的应用。成函数在某些组合数学的问题中的应用。 本节介绍生成函数在本节介绍生成函数在组合组合中的应用和指数生成函数中的应用和指数生成函数在在排列排列中的应用，主要是计数问题，也有部分方案方法中的应用，主要是计数问题，也有部分方案方法问题。问题。 考虑三个不同的物体考虑三个不同的物体a、b、c的选取方法。的选取方法。 如果对选取方

37、法的个数感兴趣，而不是对不同的选如果对选取方法的个数感兴趣，而不是对不同的选取方法感兴趣，则可令取方法感兴趣，则可令a=b=c=1，有，有 23 (1)(1)(1)1()()()axbxcxabc xabbcca xabc x 323 (1)(1)(1)(1)133xxxxxxx 7.3 组合应用例17.3 在排列组合中的应用在排列组合中的应用7.3.1 在组合中的应用在组合中的应用 例例 题题例例1、有红球两只，白球、黄球各一只，试求有红球两只，白球、黄球各一只，试求有多少种不同的组合方案。有多少种不同的组合方案。随机组合随机组合 解：解：设设r, w, y分别代表红球，白球和黄球。分别代表

38、红球，白球和黄球。由此可见，除一个球也不取的情况外，有：由此可见，除一个球也不取的情况外，有：(a)取一个球的组合取一个球的组合数为三，即分别取红，白，黄，三种；数为三，即分别取红，白，黄，三种；(b)取两个球的组合数为取两个球的组合数为四，即两个红的，一红一黄，一红一白，一白一黄；四，即两个红的，一红一黄，一红一白，一白一黄；(c)取三个取三个球的组合数为三，即两红一黄，两红一白，一红一黄一白；球的组合数为三，即两红一黄，两红一白，一红一黄一白；(d)取四个球的组合数为一，即两红一黄一白。取四个球的组合数为一，即两红一黄一白。令取令取i个球的组合数为个球的组合数为ai，则序列，则序列a0,a

39、1,a2,a3,a4的生成函数为的生成函数为故共有故共有1+3+4+3+1=12（或（或322=12）种组合方式。）种组合方式。22222222234(1)(1)(1)(1)(1)1()()()( )(1)(1)1343rrwyrrywywrywrryrwywr yr wrywr ywf xxxxxxxx 7.3 组合应用例27.3 在排列组合中的应用在排列组合中的应用7.3.1 在组合中的应用在组合中的应用 例例 题题例例2、n个完全一样的球放到个完全一样的球放到m个有标志的盒个有标志的盒子中，不允许有空盒，问有多少种不同的方子中，不允许有空盒，问有多少种不同的方案？其中案？其中nm 重复组

40、合重复组合 解：解：由于不允许有空盒，令由于不允许有空盒，令n个球放到个球放到m个有标志的盒子的方案个有标志的盒子的方案数为数为an，序列，序列an对应的生成函数为对应的生成函数为f(x)。则。则222000( )(.)(.).(.)1 (1)11 11 1111mmnmnn mnnn mnnn mnnf xxxxxxxxmnxxnxmnnxxnnmnnxxmmnam故故7.3 组合应用例37.3 在排列组合中的应用在排列组合中的应用7.3.1 在组合中的应用在组合中的应用 例例 题题例例3、某单位有某单位有8个男同志，个男同志，5个女同志，现要个女同志，现要组织一个由数目为偶数的男同志，和数

41、目不少组织一个由数目为偶数的男同志，和数目不少于于2的女同志组成的小组，试求有多少种组成的女同志组成的小组，试求有多少种组成方式。方式。随机组合随机组合 解：解：令令an为从为从8位男同志中抽取出位男同志中抽取出n个的允许组合数。由于要男个的允许组合数。由于要男同志的数目必须是偶数，故序列同志的数目必须是偶数，故序列an对应的生成函数为对应的生成函数为f(x)=(1+x)8+(1-x)8/2类似女同志的允许组合数对应的生成函数为类似女同志的允许组合数对应的生成函数为g(x)=(1+x)5-(1+5x)令令cn为为符合要求的为为符合要求的n个人组成的小组的数目，个人组成的小组的数目，由乘法法则，

42、由乘法法则，序序列列cn对应的生成函数为对应的生成函数为h(x)=f(x)g(x)=(1+x)8+(1-x)8(1+x)5-(1+5x)/2故总的组成方式数目故总的组成方式数目为为12826=3328。7.3 组合应用例47.3 在排列组合中的应用在排列组合中的应用7.3.1 在组合中的应用在组合中的应用 例例 题题例例4、证明从证明从n个不同的物体中允许重个不同的物体中允许重复 地 选 取复 地 选 取 r 个 物 体 的 方 式 数 为个 物 体 的 方 式 数 为f(n,r)=c(n+r-1,r) 。 证明：证明：设设ar表示从表示从n个不同的物体中允许重复的选取个不同的物体中允许重复的

43、选取r个物体的个物体的方式数。序列方式数。序列ar的生成函数为的生成函数为20001( )(1.)(1)1(1).(1)()!(1).(1)!11( , )nnnrrrrrrrf xxxxxnnnrxrn nnrxrnrxrnraf n rr 故故7.3 组合应用例57.3 在排列组合中的应用在排列组合中的应用7.3.1 在组合中的应用在组合中的应用 例例 题题例例5、求从求从n个不同物体中允许重复地选取个不同物体中允许重复地选取r个个物体，但每个物体出现偶数次的方式数。物体，但每个物体出现偶数次的方式数。 解：解：设设ar为所求的方式数。由于每个物体出现偶数次，故可用为所求的方式数。由于每个

44、物体出现偶数次，故可用因子因子(1+x2+x4+)示某一物体可以不选，或选取示某一物体可以不选，或选取2次，或选取次，或选取4次，次，。因此序列。因此序列ar的生成函数为的生成函数为 24222462202( )(1.)1(1)11211.12311nnnrrrrf xxxxxnnnnrxxxxrnrxrnrar 故故7.3 组合应用例67.3 在排列组合中的应用在排列组合中的应用7.3.1 在组合中的应用在组合中的应用 例例 题题例例6、在一个书架上共有在一个书架上共有16本书，其中本书，其中4本是高等数学，本是高等数学，3本是普通物理，本是普通物理，4本是本是数据结构，数据结构，5本是离散

45、数学。求从中选取本是离散数学。求从中选取r本数的方式数，其中本数的方式数，其中r=12。解：解：这实际上是求重集这实际上是求重集4*m,3*p,4*s,5*d的的12组合数。组合数。设设ar是选取是选取r本书的方式数。由于高等数学最多只能选取本书的方式数。由于高等数学最多只能选取4本，本，普通物理最多只能选取普通物理最多只能选取3本，数据结构最多只能选取本，数据结构最多只能选取4本，离散本，离散数学最多只能选取数学最多只能选取5本，故序列本，故序列ar的生成函数为的生成函数为取取f(x)展开式中展开式中xr的系数即为所求的方式数。当的系数即为所求的方式数。当r=12时，时，x12的系的系数为数

46、为34，即，即 a12=34。2342323423452345678910111213141516( )(1)(1)(1)(1)14102034506576807665503420104f xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx 7.3 组合应用例77.3 在排列组合中的应用在排列组合中的应用4.3.1 在组合中的应用在组合中的应用 例例 题题例例7、现有现有2n个个a，2n个个b，2n个个c，求从它们，求从它们之中选出之中选出3n个字生成的不同的方式数。个字生成的不同的方式数。解：解：这个问题实际上是求重集这个问题实际上是求重集2n*a,2n*b,2n*c的的3n

47、组合数。组合数。设设ar为所求的方式数。则序列为所求的方式数。则序列ar的生成函数为的生成函数为2233213210214263021426303( )(1.)1( 3)( 4).( 31)11()1!3 4 . (2)1 331!21 332321322nnnkknnnkknnnkknf xxxxxkxxxkkxxxxkkxxxxnnxr 显显然然，上上式式中中的的系系数数为为故故33213322nnnna时时，有有7.3 排列应用例87.3 在排列组合中的应用在排列组合中的应用4.3.2 在排列中的应用在排列中的应用 例例 题题例例8、由由1,2,3,4四个数字组成的五位数中，四个数字组成

48、的五位数中，要求数要求数1出现次数不超过出现次数不超过2次，但不能不出现；次，但不能不出现；2出现不超过出现不超过1次；次；3出现次数可达出现次数可达3次，也可次，也可不出现；不出现；4出现次数为偶数。求满足上述条出现次数为偶数。求满足上述条件的数的个数。件的数的个数。容斥原理容斥原理 解：解：设满足条件的设满足条件的r位数的个数为位数的个数为ar，序列，序列ar的指数母函数为的指数母函数为由此可见满足条件的由此可见满足条件的5位数位数ar=215个。个。exxxxxxxfx xxx xxxxxxxx xxxxxx xxxx 22324672323452345678910( )()(1)(1)

49、(1)1!2!1!2!3!2!4!31271()(1)223248481445843433232448171114828848288xxxxxx xxxx 2345678910518642156451!2!3!4!5!6!17851407650126007!8!9!10!7.3 排列应用例97.3 在排列组合中的应用在排列组合中的应用4.3.2 在排列中的应用在排列中的应用 例例 题题例例9、求求1,3,5,7,9五个数字组成的五个数字组成的n位数的个位数的个数，要求其中数，要求其中3,7出现的次数为偶数，其他出现的次数为偶数，其他1,5,9出现的次数不加限制出现的次数不加限制。 解：解：设满

50、足上述条件的设满足上述条件的r位数的个数为位数的个数为ar，序列，序列ar的指数母函数为的指数母函数为exxxxxxxxxxxxennnnnnnnxxxxfx xxxexxx eefx eeeeeeeeexx xnnn24232323242322353000( )(1.) (1.)2!4!2!3!1.2!3!11.()2!4!2111( )()(2)(2)444153(24! nnnnnnnxn a01)(52 31)4!1(52 31)4 7.3 排列应用例107.3 在排列组合中的应用在排列组合中的应用7.3.2 在排列中的应用在排列中的应用 例例 题题例例10、证明从证明从n个不同的物体

51、中允许重复地个不同的物体中允许重复地选取选取r个物体的排列数为个物体的排列数为nr。 证明：证明：这个问题实际上是证明重集这个问题实际上是证明重集b=*b1,*b2,*bn的的r排列数为排列数为nr。设。设ar为所求的排列数。则序列为所求的排列数。则序列ar的指数母函数为的指数母函数为rnerxnnxrrrrxxfxxrx eenr an20( )(1.)2!()!故故有有7.3 排列应用例114.3 在排列组合中的应用在排列组合中的应用4.3.2 在排列中的应用在排列中的应用 例例 题题例例11、用红、白、绿三种颜色给用红、白、绿三种颜色给1n棋盘棋盘中的正方形着色，要求偶数个正方形着红中的

52、正方形着色，要求偶数个正方形着红色，而着白色和绿色的正方形个数不加限色，而着白色和绿色的正方形个数不加限制，求不同的着色方式数。制，求不同的着色方式数。 证明：证明：若用若用r,w和和g分别表示红、白和绿三种颜色，则该问题分别表示红、白和绿三种颜色，则该问题实际上是求重集实际上是求重集b=*r,*w,*g的的n排列数，其中要求排列数，其中要求r出出现偶数次。设现偶数次。设an为所求的排列数。则序列为所求的排列数。则序列an的指数母函数为的指数母函数为exxxxxnnnnnnnnnnxxxfxx eeeeexx nnx n a242223000( )(1.)(1.)2!4!2!11()()221

53、32!1312!1312故故有有7.3 排列应用例127.3 在排列组合中的应用在排列组合中的应用7.3.2 在排列中的应用在排列中的应用 例例 题题例例12、在所有的在所有的n位数中，包含数字位数中，包含数字3,8,9，但不包含数字但不包含数字0,4的数有多少？的数有多少？ 解：解：这个问题实际上是求重集这个问题实际上是求重集b=*1,*2,*3,*5,*6,*7,*8, *9的的n排列数，其中要排列数，其中要求求3,8,9至少出现一次，而其他的数不加限制。设符合题意的数至少出现一次，而其他的数不加限制。设符合题意的数有有an个。则序列个。则序列an的指数生成函数为的指数生成函数为exxxx

54、xxxxxxnnnnnnnnnnnxxxfxxx eeeeee eeeex n a352323532587650( ).1.2!3!2!(1)(331)3383 73 65!83 73 65 故故有有7.3 排列应用例134.3 在排列组合中的应用在排列组合中的应用4.3.2 在排列中的应用在排列中的应用 例例 题题例例13、求求1,2,3,4,5五个数字组成的五个数字组成的r位数位数的个数，要求其中的个数，要求其中1出现的次数与出现的次数与2出现出现的次数的和必须是偶数。的次数的和必须是偶数。 解：解：设设an为符合题意的个数。由于为符合题意的个数。由于1出现的次数与出现的次数与2出现的次数

55、出现的次数的和为偶数，可分为两种情况：的和为偶数，可分为两种情况：1出现的次数与出现的次数与2出现的次数都为偶数；出现的次数都为偶数；1出现的次数与出现的次数与2出现的次数都为奇数。出现的次数都为奇数。由加法法则知，序列由加法法则知，序列an的指数生成函数为的指数生成函数为exxxxxxxxnnnnnxxxfxxxxx xxeeeeee eex n a2324223352225330( )1.1.2!4!2!.1.3!5!2!2221512!1512 故故有有 这是生成函数的应用实例之一。整数的拆分就是把整数这是生成函数的应用实例之一。整数的拆分就是把整数分成若干个正整数部分，并且不考虑各部分

56、的次序，不同的分成若干个正整数部分，并且不考虑各部分的次序，不同的拆分方法的总数叫拆分方法的总数叫拆分数拆分数p(n) 。相当于把。相当于把n个无区别的球放个无区别的球放到到1mn个无标志的盒子中的方法数。个无标志的盒子中的方法数。 7.4 整数的拆分概念7.4 整数的拆分整数的拆分xxxxxxxxxxxxxxx23224362345611111.1.1.123457.如如： 7.4 整数的拆分定理47.4 整数的拆分整数的拆分定理定理 7.4设设a,b,c.为大于为大于0的整数，则的整数，则1/(1-xa)(1-xb)(1-xc)的级数展开式中的级数展开式中xn的系数等于把正整数的系数等于把

57、正整数n拆分为拆分为a,b,c的和的方法数的和的方法数p(n) 。证明：证明：注意到注意到如果项如果项xn是由是由x3a, xb, x2c,的乘积所组成的的乘积所组成的 ，则，则于是，每当于是，每当n可以拆分为可以拆分为a,b,c的和时，的和时， xn就会出现，这就证明了就会出现，这就证明了定理的结论。定理的结论。abcaabbccxxxxxxxxx22211111.1.1.naaabcc.7.4 整数的拆分例17.4 整数的拆分整数的拆分例例 题题例例1、若有若有1克、克、2克、克、3克、克、4克的砝克的砝码各一枚，问能称出哪几种重量？有码各一枚，问能称出哪几种重量？有几种可能方案？几种可能

58、方案？ 证明：证明：我们采用如下办法来产生拆分数的生成函数：我们采用如下办法来产生拆分数的生成函数：从右端的生成函数知从右端的生成函数知能能称出从称出从1克到克到10克的克的重量重量，系数便是方案，系数便是方案数。数。例如右端有例如右端有2x5 项，即称出项，即称出5克的方案有克的方案有2种种，5=2+3=1+4。同样同样6=1+2+3=2+4，10=1+2+3+4，即称出，即称出6克的方案有克的方案有2种种，称，称出出10克的方案有克的方案有1种种。234233472345678910(1)(1)(1)(1)(1)(1)122222xxxxxxxxxxxxxxxxxxxx 7.4 整数的拆分

59、例27.4 整数的拆分整数的拆分例例2、求用求用1分、分、2分、分、3分的邮票贴分的邮票贴出不同数值的方案数。出不同数值的方案数。 解：解：因邮票允许重复，故生成函数为因邮票允许重复，故生成函数为以其中以其中x4为例，其系数为为例，其系数为4，即，即4拆分成拆分成1、2、3之和的拆分数为之和的拆分数为4，即即f xxxxxxxxxxxxxxxxxxxxx1222436232456234563( )(1.)(1.)(1.)11111111123457. 分分分分分分41 1 1 11 121322 例例 题题7.4 整数的拆分例37.4 整数的拆分整数的拆分例例3、若有若有1克的砝码克的砝码3枚

60、，枚，2克的克的4枚，枚，4克克的的2枚，问能称出哪些重量？各有几种方枚，问能称出哪些重量？各有几种方案？案？ 解：解：上面的上面的1+x4 +x8项表示项表示4克砝码只有两枚，或不取，或取一枚，或克砝码只有两枚，或不取，或取一枚，或取取2枚。枚。x8项的系数为项的系数为5，说明称，说明称8克的方案有克的方案有5种种 ：f xxxxxxxxxx xxxxxx xxxxxxx xxxxxxx xxxxxx xxx23246848234567891011482345678910111122131415164( )(1)(1)(1)(122222222)(1)1223344555544332克克3