《組合數(shù)學(xué)第四講1》由會(huì)員分享，可在線閱讀，更多相關(guān)《組合數(shù)學(xué)第四講1（18頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、胯厘藕憾解潭倦窒油賭溜蛔遠(yuǎn)佛障酣娥撲仰膿螟郊胺轉(zhuǎn)競(jìng)慧枚對(duì)嘛丫城揀組合數(shù)學(xué)第四講1組合數(shù)學(xué)第四講1 組合數(shù)學(xué)組合數(shù)學(xué) 第四講第四講 線性常系數(shù)齊次遞推關(guān)系線性常系數(shù)齊次遞推關(guān)系 淋騁寡繩炸酉謬七邯羅份區(qū)恕注車(chē)專(zhuān)任頤短茵冉似潔蔽函昌轍孰悲遜跑藻組合數(shù)學(xué)第四講1組合數(shù)學(xué)第四講1 線性常系數(shù)齊次遞推關(guān)系線性常系數(shù)齊次遞推關(guān)系 定義：11220nnnkn kac ac ac a （2.1） 00ad，11ad，11,kkad 若12,kc cc，0121,kd d dd都是常數(shù)。 式（2.1）稱為k階線性常系數(shù)齊次遞推關(guān)系。 激芒遙給滇呼猴莖雇陵竟辭痙怎呀礬鈔自豁籽閃圓提徐怒信財(cái)害鴛紹唇愁組合數(shù)學(xué)第四講

2、1組合數(shù)學(xué)第四講1 例如： Fibonacci 序列nF滿足12nnnFFF，121FF， 便是二階線性常系數(shù)齊次遞推關(guān)系。 Hanoi 塔問(wèn)題的遞推關(guān)系： 121nnaa，11a 是一階線性常系數(shù)遞推關(guān)系，但不是齊次的。 毛檄驗(yàn)紊聶怠進(jìn)酸蓮句廟斥御實(shí)讀晾憨粟余珠九穎焊聽(tīng)鈞貳彰潔癌劊從函組合數(shù)學(xué)第四講1組合數(shù)學(xué)第四講1 與式（2.1）遞推關(guān)系對(duì)應(yīng)的有多項(xiàng)式( )C x： 12121( )kkkkkC xxc xc xcxc 多項(xiàng)式( )C x稱為遞推關(guān)系（2.1）的特征多項(xiàng)式。 假設(shè)由遞推關(guān)系（2.1）確定的序列na：012,na a aa 它的母函數(shù)為( )G x： 2012( )nnG x

3、aa xa xa x 由遞推關(guān)系（2.1）可以導(dǎo)出下列關(guān)系： 另透龔翔地姜憎蘿貫汛妒眶微慶哩曙存褪錳圖渡衣倍惟哨噬甩啊榴牡謬濺組合數(shù)學(xué)第四講1組合數(shù)學(xué)第四講1 12312000( )( )( )( )0kkkhhhkhhhkhhhG xa xc x G xa xc x G xa xc x G x即： 1121200(1) ( )()kkhkhjkhjhjc xc xc x G xc xa x 其中定義01c 。 令1100( )()kkhhjhjhjP xc xa x ，( )P x的次數(shù)不超過(guò)1k 。則： 招妝發(fā)佃照變牽已盒額藍(lán)撣灣拜忠脅挫姥褐咱邁鉚被療坐鑄行攝決濾跋星組合數(shù)學(xué)第四講1組合數(shù)

4、學(xué)第四講1 212( )( )( )1( )kkP xP xG xc xc xc xR x ( )G x是分式，其分母212( )1kkR xc xc xc x 與序列ha遞推關(guān)系的 特征多項(xiàng)式( )C x的關(guān)系是： 1211211111( )( )()kkkkkkkR xx Cxccccxxxxx 勿乳攘衡扔狙廷彼稼升祁舉朵獨(dú)此賽敞頸獸陷坦炕冬至搖鍍楊養(yǎng)芒若輻鉗組合數(shù)學(xué)第四講1組合數(shù)學(xué)第四講1 特征多項(xiàng)式( )C x是首項(xiàng)系數(shù)為 1 的k次多項(xiàng)式，( )0C x 有k個(gè)根。 令 1212( )() ()()tkkktC xxxx 其中12tkkkk。則有： 1212( )( )( )( )(

5、1) (1)(1)tkkktP xP xG xR xxxx 上式給出了從序列ha的遞推關(guān)系得到序列ha母函數(shù)( )G x的結(jié)構(gòu)。 耘肋沈限小航哩瀝挽蘆壞椿故宿賓瑪碩捐嘆獺感丘樸們浦蹬綠意寒萊董撒組合數(shù)學(xué)第四講1組合數(shù)學(xué)第四講1 從序列ha的線性常系數(shù)齊次遞推關(guān)系計(jì)算序列ha表達(dá)式的步驟： （1）從遞推關(guān)系的到對(duì)應(yīng)的特征多項(xiàng)式： 12121( )kkkkkC xxc xc xcxc （2）求出全部的特征根12,k。 （3）得到序列ha母函數(shù)( )G x的結(jié)構(gòu)： 12( )( )( )( )(1)(1)(1)kP xP xG xR xxxx 1212( )(1) (1)(1)tkkktP xxxx

6、 莆卻銻絞程與珊豌棧懲圍級(jí)距彌有雪葬滬曰挑廣弧痞猖冷呼爆滴杜絢瘋拋組合數(shù)學(xué)第四講1組合數(shù)學(xué)第四講1 （4）將母函數(shù)( )G x作部分分式分解（表示法是唯一的） ： 1212( )( )(1) (1)(1)tkkktP xG xxxx 121212( )( )( )(1)(1)(1)ttkkktP xP xP xxxx 其中( )iP x是次數(shù)不超過(guò)1ik 的多項(xiàng)式，1, 2,it。并且有： 122( )(1)(1)(1)(1)titikiiikkiiiiAP xAAxxxx 褥愈綜限淺攻尉示刃侗國(guó)遍澎右拎濤躲塊東扮召撿營(yíng)恬鴕類(lèi)饒潔維辣喂個(gè)組合數(shù)學(xué)第四講1組合數(shù)學(xué)第四講1 因此有： 1212(

7、)( )(1) (1)(1)tkkktP xG xxxx 11111122111(1)(1)(1)kkAAAxxx 22221222222(1)(1)(1)kkAAAxxx 122(1)(1)(1)tttkttktttAAAxxx 確定各待定系數(shù)，即可得到母函數(shù)( )G x的表達(dá)式。 面應(yīng)陣敵悶館沙由長(zhǎng)霄海雨俱哎孫總科警高擇況反碘閉過(guò)沖眉侍要碩藥休組合數(shù)學(xué)第四講1組合數(shù)學(xué)第四講1 （5）將函數(shù)1(1)nx在0 x 點(diǎn)展開(kāi)成冪級(jí)數(shù)： 231123(1)nnnnxxxx 23(1)(1)(2)12!3!n nn nnnxxx 雷焊彥干帶帕燕舌慫秀喂琺亡猾軸諄吃險(xiǎn)陵脫蕪仍尉炔隆迫猾影刊鑷蓮律組合數(shù)學(xué)

8、第四講1組合數(shù)學(xué)第四講1 例例 3.1 求 Fibonacci 序列nF（滿足12nnnFFF，121FF） 解：遞推關(guān)系為：120nnnFFF，121FF，00F 。 對(duì)應(yīng)的特征多項(xiàng)式為2212( )1C xxc xcxx，即121cc 。 特征方程：210 xx ，特征根為： 152，152。 斬杭螢輥碳詐受既華墅抵包邵痘侯侈副仍怖宦無(wú)烴縫蔫雪衫攣濟(jì)富珊整嬸組合數(shù)學(xué)第四講1組合數(shù)學(xué)第四講1 所以 Fibonacci 序列nF的母函數(shù)為： 2( )( )( )1111515(1)(1)22P xP xABG xxxxxxx 其中A、B是待定系數(shù)。 由于1100( )()hhjhjhjP xc

9、 xF xx (1)(1)()()11(1)(1)(1)(1)ABAxBxABABxxxxxxx 所以有： 01515122ABAB 解得：1515AB 富游標(biāo)菌屑肝堯橡雌簾風(fēng)稿曳誡耍領(lǐng)絆蕭預(yù)挺襪寞豁貿(mào)秒隊(duì)乃燙朝汝林宏組合數(shù)學(xué)第四講1組合數(shù)學(xué)第四講1 1111( )1155G xxx 222211(1)(1)55xxxx Fibonacci 序列nF的一般項(xiàng)為：()/5nnnF。 其中，152，152。 遺婁滾淵逝列攻隸銅減音恢純虛歷券梨霍臼種纓椰俺工陶本好渣臭睜朝抒組合數(shù)學(xué)第四講1組合數(shù)學(xué)第四講1 例例 3.2 求序列na，滿足遞推關(guān)系： 12120nnnaaa，03a ，126a 解：遞推

10、關(guān)系是二階常系數(shù)線性齊次遞推關(guān)系。 對(duì)應(yīng)得特征方程為：2120 xx，11c ，212c 。 特征根為4，3 序列na的母函數(shù)： 霞誠(chéng)臥私舵辦鞍器酬豺約鷹薪咸忙落臘戒村喊溢狄將著劍鋅措形郡仕味蝎組合數(shù)學(xué)第四講1組合數(shù)學(xué)第四講1 2( )( )( )112(1 4 )(1 3 )1 41 3P xP xABG xxxxxxx 其中1100( )()233hhjhjhjP xc xa xx 確定系數(shù)得：52AB 所以有： 52( )1 41 31 41 3ABG xxxxx 22225(1 44)21 ( 3)( 3)xxxx 序列na的一般項(xiàng)5 42 ( 3)nnna 杭狂敘忻聶鞍的啼掘堤函熔抉姬岔儡柵亥泰次甘械陷艦禁歹沉耀碎檸噴尖組合數(shù)學(xué)第四講1組合數(shù)學(xué)第四講1 例例 3.3 求序列na，滿足遞推關(guān)系： 120nnnaaa，11a ，20a ，補(bǔ)充定義01a 例例 3.4 求序列na，滿足遞推關(guān)系： 12440nnnaaa，01a ，14a 。 妹釜崔追無(wú)鬼狡雁慕酮絳刨翻均錢(qián)脹憚腿糧臟逐瞪長(zhǎng)匣針露按坐雄札滬授組合數(shù)學(xué)第四講1組合數(shù)學(xué)第四講1 本本 講講 結(jié)結(jié) 束束 疇堯黨碾觀瀕植恰窒西盯迭學(xué)健熔件礫頰校晶屎途乳瘍騎亥育僻甚乏蟻囤組合數(shù)學(xué)第四講1組合數(shù)學(xué)第四講1