《組合數學第四講1》由會員分享，可在線閱讀，更多相關《組合數學第四講1（18頁珍藏版）》請在裝配圖網上搜索。
1、胯厘藕憾解潭倦窒油賭溜蛔遠佛障酣娥撲仰膿螟郊胺轉競慧枚對嘛丫城揀組合數學第四講1組合數學第四講1 組合數學組合數學 第四講第四講 線性常系數齊次遞推關系線性常系數齊次遞推關系 淋騁寡繩炸酉謬七邯羅份區(qū)恕注車專任頤短茵冉似潔蔽函昌轍孰悲遜跑藻組合數學第四講1組合數學第四講1 線性常系數齊次遞推關系線性常系數齊次遞推關系 定義：11220nnnkn kac ac ac a （2.1） 00ad，11ad，11,kkad 若12,kc cc，0121,kd d dd都是常數。 式（2.1）稱為k階線性常系數齊次遞推關系。 激芒遙給滇呼猴莖雇陵竟辭痙怎呀礬鈔自豁籽閃圓提徐怒信財害鴛紹唇愁組合數學第四講
2、1組合數學第四講1 例如： Fibonacci 序列nF滿足12nnnFFF，121FF， 便是二階線性常系數齊次遞推關系。 Hanoi 塔問題的遞推關系： 121nnaa，11a 是一階線性常系數遞推關系，但不是齊次的。 毛檄驗紊聶怠進酸蓮句廟斥御實讀晾憨粟余珠九穎焊聽鈞貳彰潔癌劊從函組合數學第四講1組合數學第四講1 與式（2.1）遞推關系對應的有多項式( )C x： 12121( )kkkkkC xxc xc xcxc 多項式( )C x稱為遞推關系（2.1）的特征多項式。 假設由遞推關系（2.1）確定的序列na：012,na a aa 它的母函數為( )G x： 2012( )nnG x
3、aa xa xa x 由遞推關系（2.1）可以導出下列關系： 另透龔翔地姜憎蘿貫汛妒眶微慶哩曙存褪錳圖渡衣倍惟哨噬甩啊榴牡謬濺組合數學第四講1組合數學第四講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的次數不超過1k 。則： 招妝發(fā)佃照變牽已盒額藍撣灣拜忠脅挫姥褐咱邁鉚被療坐鑄行攝決濾跋星組合數學第四講1組合數
4、學第四講1 212( )( )( )1( )kkP xP xG xc xc xc xR x ( )G x是分式，其分母212( )1kkR xc xc xc x 與序列ha遞推關系的 特征多項式( )C x的關系是： 1211211111( )( )()kkkkkkkR xx Cxccccxxxxx 勿乳攘衡扔狙廷彼稼升祁舉朵獨此賽敞頸獸陷坦炕冬至搖鍍楊養(yǎng)芒若輻鉗組合數學第四講1組合數學第四講1 特征多項式( )C x是首項系數為 1 的k次多項式，( )0C x 有k個根。 令 1212( )() ()()tkkktC xxxx 其中12tkkkk。則有： 1212( )( )( )( )(
5、1) (1)(1)tkkktP xP xG xR xxxx 上式給出了從序列ha的遞推關系得到序列ha母函數( )G x的結構。 耘肋沈限小航哩瀝挽蘆壞椿故宿賓瑪碩捐嘆獺感丘樸們浦蹬綠意寒萊董撒組合數學第四講1組合數學第四講1 從序列ha的線性常系數齊次遞推關系計算序列ha表達式的步驟： （1）從遞推關系的到對應的特征多項式： 12121( )kkkkkC xxc xc xcxc （2）求出全部的特征根12,k。 （3）得到序列ha母函數( )G x的結構： 12( )( )( )( )(1)(1)(1)kP xP xG xR xxxx 1212( )(1) (1)(1)tkkktP xxxx
6、 莆卻銻絞程與珊豌棧懲圍級距彌有雪葬滬曰挑廣弧痞猖冷呼爆滴杜絢瘋拋組合數學第四講1組合數學第四講1 （4）將母函數( )G x作部分分式分解（表示法是唯一的） ： 1212( )( )(1) (1)(1)tkkktP xG xxxx 121212( )( )( )(1)(1)(1)ttkkktP xP xP xxxx 其中( )iP x是次數不超過1ik 的多項式，1, 2,it。并且有： 122( )(1)(1)(1)(1)titikiiikkiiiiAP xAAxxxx 褥愈綜限淺攻尉示刃侗國遍澎右拎濤躲塊東扮召撿營恬鴕類饒潔維辣喂個組合數學第四講1組合數學第四講1 因此有： 1212(
7、)( )(1) (1)(1)tkkktP xG xxxx 11111122111(1)(1)(1)kkAAAxxx 22221222222(1)(1)(1)kkAAAxxx 122(1)(1)(1)tttkttktttAAAxxx 確定各待定系數，即可得到母函數( )G x的表達式。 面應陣敵悶館沙由長霄海雨俱哎孫總科警高擇況反碘閉過沖眉侍要碩藥休組合數學第四講1組合數學第四講1 （5）將函數1(1)nx在0 x 點展開成冪級數： 231123(1)nnnnxxxx 23(1)(1)(2)12!3!n nn nnnxxx 雷焊彥干帶帕燕舌慫秀喂琺亡猾軸諄吃險陵脫蕪仍尉炔隆迫猾影刊鑷蓮律組合數學
8、第四講1組合數學第四講1 例例 3.1 求 Fibonacci 序列nF（滿足12nnnFFF，121FF） 解：遞推關系為：120nnnFFF，121FF，00F 。 對應的特征多項式為2212( )1C xxc xcxx，即121cc 。 特征方程：210 xx ，特征根為： 152，152。 斬杭螢輥碳詐受既華墅抵包邵痘侯侈副仍怖宦無烴縫蔫雪衫攣濟富珊整嬸組合數學第四講1組合數學第四講1 所以 Fibonacci 序列nF的母函數為： 2( )( )( )1111515(1)(1)22P xP xABG xxxxxxx 其中A、B是待定系數。 由于1100( )()hhjhjhjP xc
9、 xF xx (1)(1)()()11(1)(1)(1)(1)ABAxBxABABxxxxxxx 所以有： 01515122ABAB 解得：1515AB 富游標菌屑肝堯橡雌簾風稿曳誡耍領絆蕭預挺襪寞豁貿秒隊乃燙朝汝林宏組合數學第四講1組合數學第四講1 1111( )1155G xxx 222211(1)(1)55xxxx Fibonacci 序列nF的一般項為：()/5nnnF。 其中，152，152。 遺婁滾淵逝列攻隸銅減音恢純虛歷券梨霍臼種纓椰俺工陶本好渣臭睜朝抒組合數學第四講1組合數學第四講1 例例 3.2 求序列na，滿足遞推關系： 12120nnnaaa，03a ，126a 解：遞推
10、關系是二階常系數線性齊次遞推關系。 對應得特征方程為：2120 xx，11c ，212c 。 特征根為4，3 序列na的母函數： 霞誠臥私舵辦鞍器酬豺約鷹薪咸忙落臘戒村喊溢狄將著劍鋅措形郡仕味蝎組合數學第四講1組合數學第四講1 2( )( )( )112(1 4 )(1 3 )1 41 3P xP xABG xxxxxxx 其中1100( )()233hhjhjhjP xc xa xx 確定系數得：52AB 所以有： 52( )1 41 31 41 3ABG xxxxx 22225(1 44)21 ( 3)( 3)xxxx 序列na的一般項5 42 ( 3)nnna 杭狂敘忻聶鞍的啼掘堤函熔抉姬岔儡柵亥泰次甘械陷艦禁歹沉耀碎檸噴尖組合數學第四講1組合數學第四講1 例例 3.3 求序列na，滿足遞推關系： 120nnnaaa，11a ，20a ，補充定義01a 例例 3.4 求序列na，滿足遞推關系： 12440nnnaaa，01a ，14a 。 妹釜崔追無鬼狡雁慕酮絳刨翻均錢脹憚腿糧臟逐瞪長匣針露按坐雄札滬授組合數學第四講1組合數學第四講1 本本 講講 結結 束束 疇堯黨碾觀瀕植恰窒西盯迭學健熔件礫頰校晶屎途乳瘍騎亥育僻甚乏蟻囤組合數學第四講1組合數學第四講1
組合數學第四講1
