（运筹学与控制论专业论文）发生函数在组合恒等式中的应用.pdf

发生函数方法在组合恒等式中的应用 学位论文完成日期： 指导教师签字： 答辩委员会成员签字： i v 一j 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特戛3 t j n 以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含未获得 ( 注；塑旦塑直甚他盂垩挂剔直明的：奎拦互窒2 或其他教育机构的学位或证书使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 学位论文作者签名：幸岛乍巾 签字日期：仞年岁月3 t 1 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，并同意以下 事项： l 、学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许 论文被查阅和借阅。 2 、学校可以将学位论文的全部或部分内容编入有关数据库进行检索，可以 采用影印、缩印或扫描等复制手段保存、汇编学位论文。同时授权清华大学“中 国学术期刊( 光盘版) 电子杂志社 用于出版和编入c n k i 中国知识资源总库， 授权中国科学技术信息研究所将本学位论文收录到中国学位论文全文数据库。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 协牛中聊酶翅西遥 ，7i 石 导师签字：讪。己12 签字日期：o 年y 月侈日 签字日期：, o o g 厂月纷日 发生函数方法在组合恒等式中的应用 摘要 借助发生函数证明恒等式，求解递推关系是组合数学的一个重要方法之一， 本文利用发生函数证明了有关s t i r l i n g 数的递推关系和组合数学中常见的恒 等式，并且研究了有关b e r n o u l l i 数和b e l l 数组成的发生函数的性质。 主要工作如下： 1 首先研究了无标志的第一类s t i r l i n g 数，k 阶中心阶乘数t ( n ，七) 组成的发生 函数的性质，然后又将发生函数应用到边值问题中，将三项边值问题推广到了k 项边值问题，并且给出了相关例题。 2 利用第一类s t i r l i n g 数研究了广义中心阶乘数的同余问题。 3 将两类s t i r l i n g 数和b e r n o u l l i 数作为桥梁联接两数列，进而来讨论这两数 列组成的发生函数之间的关系。 关键词：发生函数；第一类s tiri n g 数；第二类s tir1 n g 数；b e r n o u i ii 数 j l a p p l i c a t i o n so f t h eg e n e r a t i n gf u n c t i o nm e t h o di n c o m b i n a t o r i a li d e n t i t i e s a b s t r a c t i ti so n eo fi m p o r t a n tm e t h o d si nc o m b i n a t o r i c st o p r o v ei d e n t i t i e sa n ds o l v e r e c u r r e n c er e l a t i o n sb yu s i n gg e n e r a t i n gf u n c t i o n i nt h i sp a p e r , g e n e r a t i n gf u n c t i o ni s u s e dt os t u d yr e c u r r e n c er e l a t i o n sa n di d e n t i t i e so ns t i f l i n gn u m b e r s ，b e r n o u l l i n u m b e r sa n db e l ln u m b e r s t h em a i nr e s u l t so ft h et h e s i sc a nb es u m m a r i z e da s f o l l o w s ： 1 f i r s t l yg e n e r a t i n gf u n c t i o n sp r o p e r t i e so fu n s i g n e ds t i f l i n gn u m b e r so ff i r s t k i n da n dt h ec e n t r a lf a c t o r i a ln u m b e r sa r e d i s c u s s e d s e c o n d l yg e n e r a t i n gf u n c t i o ni s a p p l i e dt ot h er e s e a r c ho fb o u n d a r yv a l u ep r o b l e m sa n dt h r e et e r mb o u n d a r yv a l u e p r o b l e m si sg e n e r a l i z e dt ok - t e r mb o u n d a r yv a l u ep r o b l e m s l a s t l y , t w oe x a m p l e s a r eg i v e nt oi l l u s t r a t et h eo b t a i n e dm e t h o d 2 t h es t i f l i n gn u m b e r so fs e c o n dk i n da r ea p p l i e dt ot h er e s e a r c ho ft h e g e n e r a l i z e dc e n t r a lf a c t o r i a ln u m b e r s c o n g r u e n c er e l a t i o n s 3 t h eb e r n o u l l in u m b e r sa n dt h es t i f l i n gn u m b e r so ft w ok i n d sa r eu s e da s b r i d g et ol i n kt w os e r i e sa n dd i s c u s st h eg e n e r a t i n gf u n c t i o n so ft h et w os e r i e s k e y w o r d s ：g e n e r a t i n gf u n c t i o n ：s t ir ii n gn u m b e r so ff ir s tk i n d ： s t ir ii n gn u m b e r so fs e c o n dk i n d ：b e r n o u l lj n u m b e r ：b e i in u m b e r x 目录 l 综述1 1 1发生函数研究的背景与意义1 1 2s t i r l i n g 数研究的历史背景1 1 3 s t i r l i n g 数1 1 3 1 两类s t i r l i n g 数1 1 3 2中心阶乘数3 1 3 3 ，一相伴s t i r l i n g 数3 1 4b e r n o u l l i 数和b e l l 数4 1 4 1b e r n o u l l i 数4 1 4 2b e l l 数5 2发生函数在求递推关系中的应用9 2 1 几个有趣的递推关系9 2 2 关于递推关系的k 项边值问题1 2 3 发生函数在s t i r l i n g 数和b e r n o u l l i 数上的应用2 1 3 1 有关广义中心阶乘数的同余问题2 1 3 2 两类s t i f l i n g 数的又一性质2 2 3 3b e r n o u l l i 数在数列上的应用2 3 3 4b e l l 数和有序b e l l 数的又一计算公式2 4 参考文献2 9 致谢3 3 攻读硕士期间发表的论文3 5 柚 数 拆 1 - 3 。到了1 8 1 2 年，发生函数得到了的充分发展，表现在l a p l a c e 的经典名 著“t h e o r i ea n a l y t i q u ed e sp r o b a b i l i t e s ( 概率的解析理论) 中。j o h nr i o r d a n 于1 9 6 8 年出版了专著c o m b i n a t o r i a li d e n t i t i e s ，在这部专著中，作者运用 了发生函数的理论系统地阐述了组合恒等式中几个重要的定理。w i l f 于1 9 9 0 年 在其专著 g e n e r a t i n gf u n c t i o n 0 1 0 9 y 中论述了发生函数的各种作用：为数列 成员找出一个准确公式；求序列的平均值和其它统计性质，根据序列的发生函数 性质，找出关于这个序列的新性质：寻找递归关系；求序列的渐近公式；证明恒 等式；证明单峰性，凸性等。发生函数在证明组合恒等式时一直是一个基本而且 重要的方法 1 9 。l c o m t e t 1 4 在其著作a d v a n c e dc o m b i n a t o r i a 中对发 生函数给予了很高的评价。 1 2 s tiriin g 数研究的历史背景 s t i r l i n g 数是基本的组合数之一，由j s t i r l i n g 于1 7 3 0 年提出，并在他 的著作 m e t h o d u sd i f f e r e n t i a l i s 中首次使用。1 7 7 0 年t h i e l e 和n i e l s e n 正式运用这一名称，1 9 7 4 年l c o m t e t 1 4 对于两类s t i r l i n g 数的详细介绍体 现他的著作中，并提供了大量的参考文献又过了2 0 多年，r a y m o ds c u r r ，g l o r i a o l i r e 在文献 3 2 讨论了两类s t i r l i n g 数，并且将n 。k 的取值范围从自然数推 广到整数。1 9 9 8 年徐利治和p j s h i u e 在文献 3 2 中对以前出现的各种 s t i r l i n g 数进行了统一，给出了广义s t i r l i n g 数对的各种基本性质。刘国栋在 文献 1 6 中将广义中心阶乘数与第一类s t i r li n g 数进行了巧妙的结合，李志荣 在 2 4 中利用第一类数和第二类s t i r l i n g 数计算广义m 阶b e l l 数和广义m 阶有 序b e l l 数。人们从s t i r l i n g 数的组合意义出发的研究成果已有很多，可以参阅 文献 7 - 1 3 发生函数方法在组合恒等式中的应用 1 3 s tiriin g 数 1 3 1 两类s t i r l i n g 数 定理1 3 1t 1 4 】 第一类s t i r l i n g 数墨g ，后) 满足下面“垂直 发生函数 = 萎幼i t r = l o g k ( 1 + 力g 特别地七 刀或尼0 ，n 0 时，s i ( 刀，七) = 0 ，墨( o ，0 ) = 1 定理1 3 2 t 1 4 1无标志的第一类s t i r l i n g 数满足下面“垂直”发生函数 = 妻n = o 驰的告= 扣g 击) 伍。) 对于第一类s t i r l i n g 数墨0 ，尼) 与无标志的第一类s t i r l i n g 数( 记无标志的 第一类s t i r l i n g 数为岛g ，七) ) 由下面的定理，可以得到墨g ，尼) ，岛o ，尼) 的“水 平”发生函数。 定理1 3 3 1 4 n , k o 墨( 玎) r - - 刀! x = ( 1 + 矿2 萎( z ) ni t o , ，； n 2 0 “： 譬，( 刀埘三工l = ( 1 一矿。_ 善( z ) 。鲁 由定理1 3 3 我们可以得到墨g ，七) ，马g ，尼) 的“水平”发生函数。 定理1 3 4 ( 石) 。= z s ，( 以，k ) x ， o k s i ( n ，0 ) = s i ( o 七) = 0 ， s i ( o ，o ) = l ， 2 发生函数方法在组合恒等式中的应用 s 3 ( 刀，k ) = s 3 ( ，l 一1 ，k 一1 ) + ( ，l - 1 ) s 3 ( 以- 1 ，七) 定理1 3 6u 5 1 第一类s t i r l i n g 数s g ，尼) 满足 k - i s i ( 刀，后) = 一( n - k + i ) s l ( n - k + i ，f + l 1 - - - 0 定理1 3 7 4 1 第二类s t i r l i n g 数s 2 ( 刀，后) 满足下面“垂直 发生函数 萎”告= 扣- 1 ) 。 特别地：k 刀或刀，k 0 ，s 2 ( 刀，k ) = 0 ，s 2 ( 0 ，o ) = 1 定理1 3 8 1 第二类s t i r l i n g 数s 2 g ，k ) ，满足下面“水平 发生函数。 x “= s 2 ( 刀，后) ( x ) i k = 0 定理1 3 9 1 4 1 第二类s t i r l i n g 数s 2 g ，七) ，满足下面的“三角 递推关系 岛( 力，尼) = s 2 ( 以一l ，k 1 ) + k s 2 ( 万一l ，七) ， 力，k 1 ， 岛( 行o ) = s 2 ( o 七) = 0 ，s 2 ( o ，o ) = 1 1 3 2 中心阶乘数 本节给出关于中心阶乘数的递推关系，有关中心阶乘数的研究可参阅文献 3 4 。2 0 0 1 年，刘国栋 1 6 讨论了广义中心阶乘数的性质，在这一节我们来看 有关k 阶中心阶乘数t ( n ，k ) 和广义中心阶乘数盯( ，x ，k ) 的两个“三角 递推关 系 定理1 3 1 0 t 1 6 1k 阶中心阶乘数t ( n ，k ) 满足如下的“三角 递推关系 f ( ，七) = f ( 一2 ，k 一2 ) 一丢( 一2 ) 2 t ( n 一2 ，七) 定理1 3 1 1 1 6 j 广义中心阶乘数盯( ，x ，k ) 满足如下面的“三角递推关系 仃( ，x ，k ) = 仃( 一2 ，x 一1 ，k ) + ( 一2 x ) a ( n 一2 ，石一1 ，k 1 ) + ( 1 一x ) ( 一1 一x ) 仃( 一2 ，x 一1 ，k 一2 ) 1 3 3 ，一相伴s t i f l i n g 数 发生函数方法在组合恒等式中的应用 集合m 的后一分拆的数目表示第二类s t i r l i n g 数，其中每个块的元素是任意 的，当对块中的元素加以限制，就会得到一些新的计数。许多学者在研究这方面 的工作，赵风珍在文献 6 中对，取2 和3 时第二类相伴，一s t i r l i n g 数的特殊值。 定义1 3 1 【7 】第二类r - s t i r l i n g 数f 刀m 等于集合 l ，2 ，刀 的所有朋一划分中元 il 素，其中1 , 2 ，r 在不同的块中的划分的个数。 定义1 3 2 1 4 1 对任意整数，1 ，第二类，一相伴s t i r l i n g 数s ，( 以，七) 等于刀元集 合的所有k 一划分中，每个块至少含，个元素的划分的个数。 定理1 3 1 2 1 4 1 对任一固定的整数，1 ，第二类，一相伴s t i r l i n g 数s ，( 刀，尼) 的 “垂直“发生函数： 丢母( 万，后i t n = 去( 善告产 1 4 b e r n o u | ii 数和b el i 数 1 4 1 b e r n o u l l i 数 b e r n o u l l i 数由许多重要而有趣的性质，一直是许多专家、学者研究的热点， 在工程、物理上有广泛的应用，已得到了许多有益的结果 1 7 ，1 8 ，2 5 ，2 6 ，2 7 ，2 8 本节主要介绍两类高阶b e r n o u l l i 数的定义和基本性质。 定义1 4 1 t 1 4 】第一类高阶b e r n o u l l i b n 定义为 ( 去) 妻。：。b 丁n ( d 一其中万， 特别地有色m ，玩= l ，蜀= 一互1 ，b ：= 否1 ，日= 一面1 ，b 2 k + l = o 1 ) 定义1 4 2 【1 4 】第二类高阶b e r n o u l l i 数以定义为 ( 南心吒。n 当k = 】时右 4 争盟监：0 ， 厶一a = o 刀一a 定理1 4 1f 1 8 】设n k ，k 为正整数，则有 g 2 n - k c ：包t ) s ：g 一口，七) 一口1 6 4 ( t ) s ，g 一口，七”：o 定理1 4 2 协1 设 口。) 孑，慨) ；， c 。埒是三数列，其指数发生函数分别为 彳( f ) ，曰o l c o ) ，且 饥= 射。 g o ) ，q = e s 。g ，k ) a 。，g o k = o 舢m 彳( 。g 击) ，c 舻舢9 0 枷 定理1 4 3 呻1 设厂o ) = t ，y f rn n ( n 为正整数) ，则 厂(o)=妻，_a+ak甜la如口厶)“，to-1,2,-nk=oi、tl+kl+ + k = k ) 定理1 4 4 t 1 8 1 设刀，k n ，则 风(tg)=七r嘉(一)一。：二；。+b蚤。，jii：-；：ji)ij；：i柄-薹；p，(ng)， 曰。月g ) = l ， 曰。“b)=七：嘉(-y：一)屯+。：善；，可ijl石巧云-=一薹s。，归，“g)， 时x ) - i 1 4 2 b e l l 数 b e l l 数和有序b e l l 数在组合数学，函数论，理论物理及近似计算等方面均 5 发生函数方法在组合恒等式中的应用 有广泛的应用，对它们的研究一直受到学者的关注 2 0 ，2 l ，2 2 ，2 3 ，3 0 ，3 1 设n 个元素的集合分为非空的后个部分的划分为万g ，尼) ，称以个元素的集合 的所有划分数之和为b e l l 数，设为如) ，即6 g ) = 万g ，七) 。 定义1 4 3 【1 4 1 有序b e l l 数占g ) 是 n 全部有序划分数，即 矾) = 七! s ：g ，k ) 当刀= o ，1 ，2 ，3 ，4 ，5 ，1 0 时，占g ) 的值分别为1 ，1 ，3 ，1 3 ，7 5 ，1 0 2 2 4 7 6 0 8 定理1 4 5 眦1 设6 ( 甩) 为b e l l 数，则其指数发生函数为 妻掣一：广- ， 怠刀1 其中b o = 0 1 9 9 3 年，a i t k e n 在 2 1 证明了b e l l 数满足下面递推关系 h = 散卜 定理1 4 6 【1 9 1 设i g ) 是有序b e l l 数，则其指数发生函数为 争避。：上 - n - - 0 刀1 2 一e 。 定理1 4 7 【1 9 】设m r ( 实数) ，广义m 阶b e l l 数6 ( m g ) 和广义m 阶有序b e l l 数i ( m g ) 分别由下列展开式给出 p 广= 薹学”， ( 击) ”= 薹学“ 其中6 o ( 0 ) = 方( 。( o ) = l ，占( o g ) = 6 ( o g ) = og 1 ) ，6 ( 1 g ) = 6 ( 刀) 为b e l l 数，i ( 1 g ) = 占g ) 为有序b e l l 数。 6 发生函数方法在组合恒等式中的应用 定理1 4 8 t 3 5 1 设m r ，玎n ，则 n - i ( i ) 6 m g ) = 肌”一s 。( i t ，尼谚 ) ，6 m ( o ) = l ； 川神m 以：乳。1 病一部卜蜘t ； ( i i i ) 6 ( m g ) ：主朋t s ：( 1 ，七) 7 发生函数方法在组合恒等式中的应用 8 发生函数方法在组合恒等式中的应用 2 发生函数在求递推关系中的应用 2 1 几个有趣的递推关系 本节研究的主要内容是常见递推关系组成的发生函数的性质。 弓i 理2 1 1 t 3 3 】j o k ) - - g ( n 一1 ，k 一1 ) 一( n 1 ) i ( 万一1 ，尼) l 引理2 1 2 m 1 记歹g 后) 的发生函数为e g ) = j g ，七k k p 则 n - i v ( x ) - - 兀( x 一，) ( 1 1 1 ) l 定理2 1 1 设无标志的第一类s t i r l i n g 数8 3 g ，k ) 的发生函数为 n - i 则日。g ) = 兀g + ，) 证明： h 。g ) = s ，( t l ，尼矿 k = 0 h 。g ) = s ，g ，k ) x k = 0 ：主 ，( 珂一1 ，k 一1 ) + ( 1 1 1 扮，g 一1 ，尼b t ) = x s ，( n - 1 ，七一l b + g 一1 ) s ，g l ，七b = x s 3 ( n - l ，k - 1 ) x 扣1 + g l 压s ，( n - 1 ，七h k - - 0 k = 0 = x h 川g ) + o l 归川b ) = b + 万一l 归川g ) 所岫阱f j 础= 兀n - i i = 0i = 0 ) 所以h 。g ) = 兀号笋筹= 兀b + ，) 1 1 ，p ， 引理2 1 3 1 1 4 16 g ，七) 数满足下面“三角”递推关系 9 发生函数方法在组合恒等式中的应用 b ( n ，后) = b ( n ，七一1 ) + 6 ( 刀一1 ，j j ) 定理2 l 2 6 数的发生函数满足c g ) = 妻k = 0 6 g ，尼m oe g ) 2 而1 证明由引理2 1 3 知 e g ) ：至，k 一1 ) + 6 ( 刀一1 ，后b t ) k - - - o = 以g ) + c 一。g ) l 上式整理可得 ( 1 一x 巴g ) = c g ) 一盟、 一c 一。g ) l 1 一x 啡，= 端矧裂锱二南卦 定理2 1 3 七阶中心阶乘数f ( ，七) 的发生函数q g ) = f ( ，七k 则g 。g ) = n 偶数， n 奇数 证明：由引理1 3 3 知 g ( 功= 妻k - - 0 r ( ，后h = 妻lr ( n - 2 , k - 2 ) 一 ( 一2 ) 2r ( n - 2 , k k = o) l x tl - r j = x 2 g m _ 2 ( 功一i 1 ( 一2 ) 2 g m 一2 ( 石) = x 2 一三c 一2 ，2 g 一：c 功 当n 偶数时 1 0 1j 、l ， 1j 1 v ， + 尼 后 q q 一4 一4 一 一 x x _。l。-一 业：兀脚竽n脚 ，、【 发生函数方法在组合恒等式中的应用 当n 奇数时 综合上面两种情况 q g ) = g 小，= 百错= 甜扣，2 n - 3 n - 3 g c 工，= 。：- i 。g u 2 ：m 。+ 八( x ，) 。= 要j x 2 一三c 2 七+ ，2 n 偶数， n 奇数 定理2 1 4 广义中心阶乘数的发生函数巧( f ) = 盯( ，x ，尼) ，则 k - - o 巧o ) = f 1 【1 + r ( 2 一x + f 20 一x 胁+ 1 _ x ) 】 偶数， n - 3 卉【1 + f ( 2 七+ 3 一x ) + f ：0 一x x 2 k + 2 一x ) 】 奇数 k = 0 证明由引理1 3 4 知 巧o ) = 仃( ，x ，七 ， k - - o =l(盯1-xxn2工-一l-l，x后)c+r(n-一2x,x)|cr一(n，七-一2,2x1 2 1 ) 一1 七一l + ) 一1 。 x 一，七一2 )- r = 巧一：o ) + f ( 一x 弦1 一：o ) + f 2 ( 1 一x x n 一1 一x ) z 一：o ) = 【1 + f ( 一x ) + f 2 0 一x x n 一1 一x 帆一：o ) l 用证明定理2 1 3 类似的方法可得 巧( f ) = j ，一2 兀2b 量= 0 | l ，- 3 兀2 1 k = 0 + f ( 2 七+ 2 一z ) + f z ( 1 一x x 2 k + 1 一石) 】 偶数 + t ( 2 k + 3 一x ) + f 2 0 一工x 2 k + 2 一石) 】 n 奇数 1j 2 、i ， 1j 1 v ， + 后 七 q q 1 4 1 4 一 一 rhl厂hl竿n脚竿n脚 发生函数方法在组合恒等式中的应用 2 2 关于递推关系的k 项边值问题 递推关系在许多数学分支例如组合数学、概率论、几何学、矩阵理论等中有 着重要作用，递推关系在已知初始条件的情况下的求解问题被许多文献讨论过 3 6 - 4 1 ，但递推关系的边值情况却讨论的不多，文献 1 9 讨论了三项边值问题 当特征方程有两个不相等的特征根时的求解问题，本节试图利用发生函数的方法 来讨论递推关系的k 项边值问题。 考虑下列递推关系 a o y 。+ l + 口l y + + 口| 一l y 。一i + 2 = 吒， ( 2 2 1 ) 其中刀= 七一2 ，七一1 ，一l ，a o ，a l ，a t - l ，d 。g = 七一2 ，n 一1 ) 为已知实 数。而y 。满足边值条件 y 。2 6 0 ，y t26 ， ， ( 2 2 2 ) i y ，= b a , ，y k - l - 3 ) = “一m 3 ) 递推关系( 2 2 1 ) 与边值条件( 2 2 2 ) 构成k 项边值问题，为求解k 项边值 问题，设 厂( 名) = a o + 口l 五+ + 口t l 1 = 0 ， ( 2 2 3 ) 称( 2 2 3 ) 为k 次递推关系( 2 2 1 ) 的特征方程，其根称为k 次递推关系( 2 2 1 ) 的特征根。 为求解k 项边值问题首先给出两个发生函数： 】，g ) = y ，工，d g ) = d ，一， ( 2 2 4 ) 其中y g ) 为未知函数，d ( x ) 为已知函数。 2 2 1 三项边值问题 考虑递推关系 a o y 。“+ a l y + a 2 y 。一= 以( 刀= 1 , 2 ，n 1 ) ， 1 2 ( 2 2 5 ) 发生函数方法在组合恒等式中的应用 其中y 。满足边值条件y o = b o ，y = b 递推关系( 2 2 5 ) 的特征方程为 口o + 口l a + 口2 矛= 0 ， 用x ”分别乘( 2 2 5 ) 式等号两边并求和，得 一l一i一l ，一l 口。z y 州z 4 + 口l 儿x “+ 口2 n = l y 纠x 4 = 月l l n = ln = l 利用( 2 2 4 ) 式并整理可得 其中 d 。x “， ( 口。+ 口，x + a ：x 2 沙b ) = 尺g ) + 口。y 。x + a ：y 一。x 肌- ， 尺g ) = x d g ) + 口o b o - l - a 1 6 b x + 口1 6 x + 1 + 口2 b ，x ( 2 2 6 ) ( 2 2 7 ) ( 2 2 8 ) 下面根据特征方程( 2 2 6 ) 的根的情况分别进行讨论，因为本文讨论的是 三项边值问题，所以( 2 2 5 ) 式中a o 0 ，从而特征方程( 2 2 6 ) 无零特征根。 1 当特征方程( 2 2 6 ) 有两个不相等的非零特征根1 ，r 2 时 将1 ，r 2 分别代入( 2 2 8 ) 式可得 解方程组( 2 2 9 ) ，得 r l u + l 尺也) 一+ 1 尺( t ) f i r ( r 2 ) 一，2 尺( 1 ) 将y ly 一l 的值代入( 2 2 8 ) 有 】，( x ) = ， 尺( 工) ，2 ( 一) + x ( 1 + 1 尺( 屹) 一+ 1 尺( ) ) + x + 1 ( ，2 尺( 1 ) 一1 尺( 厂2 ) ) ( 口o + 口i x + a 2 2 2 ) 1 吃( 一) 。 再由y 。= 【x “ 】，( x ) ，就得到了数歹t j y 。) 7 2 当特征方程( 2 2 6 ) 有两个相等的非零特征根，时 首先对( 2 2 8 ) 式关于x 求导数有 1 3 ( 2 2 9 ) m n = = 矿锻m 毗“以 = 以 y y ，【 发生函数方法在组合恒等式中的应用 ( 口l + 2 a 2 曲】，( x ) + ( 口o + 口l x + a 2 x 2 ) y ( 工) = r 。( 功+ 口o y l + ( + 1 ) 口2 y - l x ，( 2 2 1 0 ) 将特征根，代入( 2 2 8 ) 和( 2 2 1 0 ) ，得 方程组( 2 2 1 1 ) 解得 lg-i r r ( ，) 一( + 1 皿) n a o ， r(r)-rr(r) 一n a 2 ，+ 1 将y ，y - l 的值代入( 2 2 8 ) 整理可得 ， = o ( 2 2 1 1 ) 脚型丛型警错等等掣坠地汜2 由y 。= i x “】，( x ) ，即求出了数列。 孑。 2 2 2k 项边值问题 一l 用x ”分别乘( 2 2 1 ) 式等号两边并求和得 口oe y 肘i x “+ 口l 一l 少h x “+ + a t l n = k - 2n = k - 2 利用( 2 2 4 ) 式整理可得 其中 ， k - ! 】，g 压 f l ( x ) = 口。包工+ 叩 l - - o + 吒- ，一2 工一一2 + 口t 一2 工一2 i = o b , x + 扭- k - i - 3 ) ，- ij 一l j ，n - k + 2 x 4 = d n = k - 2r e = k - 2 n x ”， 4 ，工= 如g ) + 口g ) + g 6 j x + 口l b 工+ + 口i - ，- 3 工- ，一3 ，一l a k - i - i x n q 包工+ ，h q l = o b i x i a t _ i x _ 扛 ，一i - t - d k - l - 3 口( 工) = y ，+ l 工“1 b i x ， 扭- ( k - 1 - 3 ) ( 2 2 1 3 ) ( 2 2 1 4 ) 纠+ 一：x k - l - 2 6 i x i - - oi = o j ， y b , x + j r 一 j = 1 k - - i - 3 ) 上一i a i x + + y t 一2 z _ 2 口。+ y 一“2 口t - i 工+ 1 + + y 一“l + 2 x 一i + ，+ 2 口f x 7 1 4 i = k - i - i m = q m 帅，咖蛳叭 h 一 儿 扣 仨 发生函数方法在组合恒等式中的应用 下面根据特征方程( 2 2 3 ) 的根的各个情况分别讨论( 类似于三项边值问 题，k 项边值问题的特征根不存在零根) i 当特征方程( 2 2 3 ) 有k 1 个不同的非零实数根时 设特征方程( 2 2 3 ) 的k - 1 个不同的非零实数根为 ，如，如，以- l ，把这 七一1 个实数根代入( 2 2 1 4 ) 整理可得 f 口瓴) = 一 d “) 一“) i 口( 如) = 一如d ( 如) 一( 如) ， 1 k 仇一。) = 一以一，d 仇一。) 一仇一。) l 方程组( 2 2 1 5 ) 的系数组成行列式，利用克莱姆法则可得 y ；= 鲁o = ，七- 2 一七+ 2 ，一七+ ，+ 2 其中 a = k i - 3 掣a i 2 ： i = 0 k - l - 3 旯1 a , 2 2 i = 0 k - l - 3 粥口，以一。 1 = 0 钟a o 斧2 a o 筏k - 一1 2 口o 旯“+ 2 口，硝 i = k - i - i 七一l 允“+ 2 口，以 七一i 旯甜“+ 2 口，豫。 l = k - l - i 4 是把 a 的第i 列换成( 一 d ( ) 一( ) 9 * e9 一 一i d ( 以一。) - p ( 2 k 一。) ) r 将 y fo = 1 + 1 ，k 一2 ，n k + 2 ，n 一尼十，+ 2 ) 的值代入( 2 2 1 4 ) 后整理可得 】，( x ) ：型芝掣业盟， 叩_ _ i = o 其中口。( x ) = 鲁石“lk 智- t - 3 。a l v - 彳* + l + 2x n - k + l + 2 ，鼻譬a 。一由儿= 【x ”】y ( x ) ，就可 以算出数列抄。) 。 发生函数方法在组合恒等式中的应用 2 当特征方程( 2 2 3 ) 有重根且都是实根( 不含零根) 设特征方程( 2 2 3 ) 的 j 个实根分别为a ( 聊。重根) 9 o 9 以( 朋，重根) ( 朋。+ m 2 + + 册，= 七一1 ) 首先看 ，对( 2 2 1 4 ) 式关于x 求( 朋，一1 ) 阶导数，可得 ( y ( 曲口，x ) = ( 如( x ) ) + 口( z ) + ( x ) ， i = 0 1 ( 】，( 功口，石) 。= ( 如( 力) 。+ 口。( 功+ “( 曲， i = 0 k - i ( 】，( 工) 口i 工) 肼1 哪= ( x d ( 功) 婀1 1 + 口m 一( 功+ ”一( 功- 将 代入 ( 2 2 1 4 )和 ( 2 2 1 7 )式，并且注意 厂( 五) = o ，f 。( a ) = 0 ，- - ，”i 。1 ( a ) = o ，整理可得 口( a ) = d ( ) 一( 丑) ， 口( 五) = ( 一a d ( ) ) - p ( ) ， 口( m l - i ) ( ) = ( 一 d ( ) ) 帆一- d ( m r - 1 ) ( ) ( 2 2 1 8 ) 式是由聊，个方程组成的方程组，对如， ，以，用与 同样的做法， 可分别得由m ：，朋，m ，个方程组成的方程组， 又因为 m l + m 2 + + 掰，= 七一1 ，可得下面尼一1 个方程组成的方程组 口( 五) = 1 d ( ) 一( ) ， 1 ：r ( r a n - 1 ) ( ) = ( d ( ) ) 朋_ 一( m l - i ) ( ) ， 口( 如) = 一如d ( 如) 一( 如) 口( 屹一1 ( 如) = ( 一如d ( 如) ) 脚z - 1 - p ( m z - i ) ( 如) ， 口( 以) = 以d ( 以) 一( 丑) ， o l 詹i - d ( t ) = ( t d ( 以) ) 鸭1 - d - 1 ( 以) 对方程组( 2 2 1 9 ) 用1 中的方法即可解出未知数 1 6 发生函数方法在组合恒等式中的应用 y ，+ l ，y ，+ 2 ，y 七一2 ，y 小2 ，y 一| | “+ 2 将其代入( 3 2 1 4 ) 即可求得】，( 力。由 y 。= 【z “】y ( x ) ，可以算出数列。) 。 3 当特征方程( 2 2 3 ) 有复根并且实根复根都有重根时，设特征方程( 2 2 3 ) 有，个实根，2 t 个复根 ( 刀。重根) 9e e $ 4 ( 咒，重根) ，c i 沏。重根) ，_ ( ，l ，重根) ( 其 中q 为c i 的共轭复数刀l + + 刀，+ 2 ( 胁l + + 朋，) = k - 1 ) 首先看对 处理的情况，我们对( 2 2 1 4 ) 式关于x 求( 疗。一1 ) 阶导数，可得 七一l ( y ( x ) 口j 一) = ( 加( 砷) 。+ 口( x ) + ( x ) ， t = 0 然后对如，厶，乃，c l c t 的做法与对 的方法类似，可分别得由 刀2 ，一3 ，n r , 2 m i , , 2 m ，个方程组成的方程组， 又因为 刀i + 刀，+ 2 ( 朋l + + 册，) = k - 1 ，这样由 ，4 ，c l c f ，可得下面七一1 个方程组 成的方程组， 口( ) = 一a d ( ) 一( ) ， a , ( n n - 1 ) ( ) = ( 一2 t d ( 2 t ) ) 旷n f l ( n n - 1 ) ( ) ， 口( 如) = 一如d ( 如) 一( 五) ， 口( 妒( 如) ：( 一如d ( 如) ) 一z n 一n z 一( 如) ， ( 2 2 2 0 ) a ( c ，) = 一c ，d ( e ，) - p ( c ，) ， 口掰f 。1 ( i ) = ( 一；- d ( 百) ) 。1 ) 一肼，q ( i ) 然后对方程组( 2 2 2 0 ) 用 1中的方法即可解出未知数 y ，+ l ，j ，+ 2 ，y h ，y 十2 ，y 一川+ 2 再将它们代入( 2 2 1 3 ) 且pn - i 求得y ( x ) 再 由y 。= 【x ”】y ( x ) ，我们就可以算出数列 儿) 7 2 2 3 有关的例题 1 7 、， x ， 一 h 矗 + 、， x o 口+ 一 协 ” x ，l 如 ，- 、 = q v x口 汹 x ，l y ，k 发生函数方法在组合恒等式中的应用 例1 求由下列递推关系决定的。 ： 2 y 斛i 一儿一2 j ，。一l + y 一2 = d 。 ( 刀= 2 ，6 ；y o = 甄= 夕7 = o 其中p 。) ：= - 1 3 ，- 6 ，3 ，1 ，- 2 。 76 解：设】，伍) = j ，一，d g ) = 4 ，由( 2 2 1 4 ) 可得 ( 2 一z 一2 x 2 + x 3 妒g ) ：x ( d ( x ) + 2 y l y l x + 2 y 2 x + y s x 7 ) ， 特征方程为2 - 2 2 形+ = o ，解得 = 1 ，如= 一1 ， = 2 。 由( 2 2 1 5 ) 可 得 其中d ( 1 ) = 一1 7 ，d ( 一1 ) = - 7 ，d ( 2 ) = 一1 4 8 。 解方程组得y l = 6 ，y 2 = 5 ，y 5 = 1 。 由( 2 2 1 6 ) 可得y ( d = 6 x + 5 x 2 + 2 x 3 + x 5 即。 ：= o ，6 ，5 ，2 010 ，o 。 例2 求有下列递推关系决定的数列。 ： y 。+ i 一2 y 。+ j ，。一l = d 。，( 刀= 1 ，5 ；y o = y 6 = o ) ， 其中p 。 5 = 01 ，5 ，一1 0 ，- - 2 ，1 ) 。 解： 65 设】，( x ) = y ，工，d g ) = z , t , x ，由( 3 2 8 ) 可得 特征方程为 - - 2 x + x 2 沙b