4第四章生成函数

1、第四章第四章 生成函数生成函数1 1 常生成函数及其应用常生成函数及其应用例例22222(1)(1)(1)1()()()rrwyrywrryrwywr yr wrywr yw 2342345678910(1)(1)(1)(1)122222xxxxxxxxxxxxxx 例例1 1 有红球有红球2 2只，白球、黄球个一只，试求有多少种只，白球、黄球个一只，试求有多少种不同的组合方案不同的组合方案例例2 2 若有若有1g1g，2g2g，3g3g，4g4g的砝码各一枚，问能称出的砝码各一枚，问能称出几种可能的重量？几种可能的重量？例例3 3 若有若有1g1g砝码砝码3 3枚，枚，2g2g砝码砝码4 4

2、枚，枚，4g4g砝码砝码2 2枚，问能称出枚，问能称出哪些重量？各有种方案？哪些重量？各有种方案？23246848(1)(1)(1)xxxxxxxxx形式幂函数形式幂函数20120(0,1,2,)( )innnnnta iA taa ta ta ta tt 定定义义设设 是是一一个个符符号号，为为实实数数，则则称称为为以以 为为未未定定元元的的一一个个形形式式幂幂级级数数. .001( ),( )( )( )(0,1,2,);2nnnnnnnnA ta tB tb tA tB tabn 注注：（）对对于于，= = （）形形式式幂幂级级数数不不存存在在收收敛敛性性问问题题. .000000111

3、0( ),( ),(1) ( )( )() ;(2) ( )( )() ;(3) ( )( )() ;(4)( );1(5)( ).1nnnnnnnnnnnnnnnnkn knknnnnnnA ta tB tb tA tB tab tA tB tab tA tB ta btA tna tA t dta tCn 对于定义对于定义形式幂级数运算形式幂级数运算00( )( ),( )( )1,( )( )nnnnnnA ta tB tb tA tB tB tA t 定义设是形式幂级数，如果存在定义设是形式幂级数，如果存在形式幂级数使得形式幂级数使得则称 是的一个逆元.则称 是的一个逆元.00( )0

4、,( )nnnA ta taA t 定定理理形形式式幂幂级级数数有有逆逆元元的的充充分分必必要要条条件件是是且且若若有有逆逆元元，则则逆逆元元唯唯一一. .0001( )( )(0)( )( )( )( )( )( )nnnnnnA ta tB tb tbA tB tA tA t BtB t 定定义义设设和和是是两两个个形形式式幂幂级级数数，则则和和的的商商为为000.nnnnnnnnna xa ta x 定义设是幂级数，则称形式幂级数定义设是幂级数，则称形式幂级数是相应的形式幂级数是相应的形式幂级数,xe例例对对于于实实函函数数写写出出它它对对应应的的形形式式幂幂级级数数. .01( ),(

5、 ).!nknA ttAtn 例设有形式幂级数求例设有形式幂级数求01( ).!nnA ttn 例例求求形形式式幂幂级级数数的的逆逆元元01( )1(0),(1)(1)(1)1.!mn nn nnnmA ttmm mmntttnn定理设是任一个有理数，则对形式幂级数定理设是任一个有理数，则对形式幂级数有有01(1)knnnkttn 常生成函数常生成函数000 ( ).nnnnnnnaA ta ta 定定义义设设是是任任一一数数列列，则则形形式式幂幂级级数数叫叫做做数数列列的的常常生生成成函函数数20nn 例求数列的常生成函数.例求数列的常生成函数.011203,9,4342,.nnnnnaaa

6、aana 例例设设求求数数列列的的通通项项公公式式常生成函数的应用常生成函数的应用12121(1,2, )(1,2, )( ).kkkknkrnkkrnjrkjMMknxxxrxaxxxrxMknaA ttt 定定理理以以表表示示不不定定方方程程中中的的未未知知数数的的可可取取值值所所成成的的集集合合，以以表表示示方方程程满满足足的的解解的的个个数数，则则是是展展开开式式中中 的的系系数数12312314888.xxxxxx 例例求求不不定定方方程程满满足足条条件件，的的非非负负整整数数解解的的个个数数1232421.xxx 例例求求方方程程的的正正整整数数解解的的个个数数312,00 xyx

7、y 例例求求由由直直线线直直线线及及直直线线所所围围成成的的三三角角形形（包包含含边边界界）的的正正点点（横横坐坐标标和和纵纵坐坐标标均均是是整整数数的的点点）的的个个数数. .312xy123zxy 令令312xyz有有(5,0),(0,5),( 5,0),(0, 5)OxyABCD 例例求求平平面面直直角角坐坐标标系系中中，以以为为顶顶点点的的正正方方形形内内（包包括括边边界界) )的的整整点点的的个个数数. .|5xyz ()( , )( , ).rrnkababr nrkrrf n kf n k例从一个 元排列中选取 个元作组合，使得组合中例从一个 元排列中选取 个元作组合，使得组合中

8、的任何两个元 和 满足条件：在原排列中 和 之间至少的任何两个元 和 满足条件：在原排列中 和 之间至少有个元，以表示作成的不同组合有个元，以表示作成的不同组合的个数，求的个数，求121,(1,2, )( ).kkknkkrnjrrkjMAa aanArMknaggA ttt 定定理理设设是是 元元集集，从从 中中可可重重复复地地选选取取个个元元作作组组合合，以以表表示示被被允允许许重重复复选选取取的的所所有有次次数数作作成成的的集集合合，以以表表示示作作成成的的组组合合的的个个数数，则则是是展展开开式式中中 的的系系数数()nr rn 例从 元集中可重复地选取个元作组合，例从 元集中可重复地

9、选取个元作组合，每个元至少取1次，求作成的可重复组合的个数.每个元至少取1次，求作成的可重复组合的个数.4 ,4 ,3 ,3 7.Sabcd 例例求求多多重重集集的的 组组合合的的个个数数2 2 车问题车问题问题描述：设问题描述：设n是任一个正整数，从一个是任一个正整数，从一个nn棋盘棋盘中删去若干个格子后所得的图形称为一个棋盘，设中删去若干个格子后所得的图形称为一个棋盘，设C是任一个棋盘，把是任一个棋盘，把k个车放在棋盘个车放在棋盘C上，使得任何上，使得任何两个车既不同行也不同列，两个车既不同行也不同列，k个车在棋盘个车在棋盘C上这样上这样这样的放置方法称为这样的放置方法称为k个车在棋盘个车

10、在棋盘C上的一种好布局上的一种好布局.以以rk(c)表示表示k个车在棋盘个车在棋盘C上的好布局数，约定上的好布局数，约定r0(c)1.例例 对于棋盘对于棋盘C： ， 求求( )kr c,( )( )kknn nCr cnk例证明：对于棋盘有例证明：对于棋盘有车多项式车多项式0 ( ,)(),( ,).kkkCR t Cr C tR t CC 定定义义设设是是任任一一个个棋棋盘盘，令令则则称称为为棋棋盘盘 的的车车多多项项式式( ).n nR t 例例求求棋棋盘盘的的车车多多项项式式例例 求棋盘求棋盘 的车多项式的车多项式R(t). ( , )( ,)( ,).CCCCCR t ctR t CR

11、 t C 定定理理设设 是是棋棋盘盘 上上的的任任一一个个格格子子，以以表表示示从从中中去去掉掉与与 同同行行和和同同列列的的全全部部格格子子后后所所得得的的棋棋盘盘，以以表表示示从从 中中去去掉掉格格子子 后后所所得得的的棋棋盘盘，则则例例 求棋盘求棋盘 的车多项式的车多项式.定义定义 设设C是任一个棋盘，从是任一个棋盘，从C中删去若干个格子后中删去若干个格子后所得的棋盘称为棋盘所得的棋盘称为棋盘C的一个子棋盘的一个子棋盘.1212121212 ( ,)( ,)( ,).CCCCCCCCCCCR t CR t CR t C 定定理理设设和和都都是是棋棋盘盘 的的子子棋棋盘盘， 由由和和拼拼成

12、成，且且和和彼彼此此分分离离，即即中中的的格格子子与与中中的的任任一一个个格格子子在在 上上即即不不同同行行也也不不同同列列，则则例例 求棋盘求棋盘 的车多项式的车多项式.例例 求棋盘求棋盘 的车多项式的车多项式.有禁位排列有禁位排列1212,(1),(1,2, )niinina aaainjjannna aaa ini 考考虑虑 个个相相异异元元的的全全排排列列，如如果果规规定定不不能能排排在在第第 个个位位置置上上，则则第第 个个位位置置对对来来说说是是一一个个禁禁止止摆摆放放的的位位置置，称称为为禁禁位位，规规定定某某些些元元素素不不能能排排在在某某些些位位置置上上的的 元元排排列列问问

13、题题称称为为 元元有有禁禁位位排排列列问问题题. . 个个相相异异元元的的重重排排问问题题就就是是一一个个有有禁禁位位排排列列问问题题，其其中中不不能能排排在在第第 位位. .( ).nnnnnRnnBRCRCRnr B 符号： 以表示带有禁格的棋盘，以符号： 以表示带有禁格的棋盘，以表示中全部非禁格所成的棋盘，以 表示表示中全部非禁格所成的棋盘，以 表示中全部禁格所成的棋盘（ 称为的禁格中全部禁格所成的棋盘（ 称为的禁格棋盘），满足所给限制条件的 元有禁位排列棋盘），满足所给限制条件的 元有禁位排列的个数位的个数位命中多项式命中多项式.nmmnnnnremnenrm 问问题题： 设设给给出出

14、一一个个 元元有有禁禁位位的的排排列列问问题题，对对应应于于带带禁禁格格的的 棋棋盘盘以以表表示示恰恰有有个个元元排排在在禁禁位位上上的的元元排排列列的的个个数数，等等于于把把 个个车车放放在在 上上，使使得得恰恰有有个个车车放放在在禁禁格格上上的的好好布布局局数数0(0) ( )( ).nmnnmmmnRnnemnnRmE te tE tR 定定义义设设是是任任一一个个带带有有禁禁格格的的棋棋盘盘，以以表表示示把把 个个车车放放在在上上，使使得得恰恰有有个个车车落落在在禁禁格格上上的的好好布布局局数数，令令，称称为为的的命命中中多多项项式式0( )( )()!(1)nnnnjjjRnnCRR

15、E tr Cnjt 定理设是任一个带有禁格的棋盘， 是定理设是任一个带有禁格的棋盘， 是的禁格棋盘，则的命中多项式为的禁格棋盘，则的命中多项式为 12121()jjjiiiiiinNN a aa ( 1)j mmjj mjeNm 121 2()()()!jjiiiji iiN a aar Cnj()! ( )jjNnjr C00( )( )()!(1)nnmjmjmjE te tr Cnjt 55 5R 例例求求如如图图所所示示的的带带有有禁禁格格的的棋棋盘盘的的命命中中多多项项式式. .12345123455,124534a a a a aaaaaa例作 个相异元的全排列，其中例作 个相异元

16、的全排列，其中不排在第 位和第 位，不排在第2位和第3位，不排在第 位和第 位，不排在第2位和第3位，不排在第5位，不排在第 位和第 位，不排在第5位，不排在第 位和第 位，不排在第 位和第 位，不排在第 位和第 位，问可以作出多少个不同的全排列？问可以作出多少个不同的全排列？ 指数生成函数及其应用指数生成函数及其应用0220100( )2!.nnnnnnnnnaa ta ta tE taa tnna 定定义义设设是是任任一一数数列列，则则形形式式幂幂级级数数称称为为数数列列的的指指数数生生成成函函数数0.nnrr 例例求求数数列列的的指指数数生生成成函函数数，其其中中 是是正正实实数数230

17、0!n nnnnrr ttnn 例例设设 是是正正实实数数，计计算算指数生成函数的应用指数生成函数的应用121,(1,2, ) ( )!.!kkknkkrjnkjMkrAa aanAraknMetE tjtr 定理设是 元集，从 中可重复定理设是 元集，从 中可重复地选取 个元作排列，如果可重复地选取 个元作排列，如果可重复选取的全部次数所成之集为 ，则作成的排列数选取的全部次数所成之集为 ，则作成的排列数是是展开式中的展开式中的.nr 例例求求 元元集集的的每每个个元元素素至至少少出出现现一一次次的的可可重重复复排排列列的的个个数数1,2,3,4662例例用用数数字字作作 位位数数，每每个个数数在在 位位数数中中出出现现的的次次数数