（计算数学专业论文）渐近计数方法及其应用.pdf

大连理工大学博士学位论文 摘要 本文利用渐近计数方法给出了一些特殊组合和式，生物序列的比对个数以及正负二 项分布逆矩的渐近值 本文主要工作可概括如下： 在第二章中，我们利用发生函数方法给出了特殊组合恒等式，并且利用渐近计数方 法进一步研究了组合和式：= o ( ；) 7 k 和麓。( ；) 击的渐近性 近几年，涉及二项式系数倒数的恒等式的研究逐渐增多，但是关于二项式系数倒数 和的渐近性，得到结果并不多在第三章我们利用发生函数方法和定积分方法建立了一 些包含二项式系数倒数以及幂和的有限和与无限和式，并且利用渐近计数方法给出了它 们的渐近值 第四章推广了r i c e 引理，利用它以及留数定理研究了交错和的渐近性，并且给出了 它们的俨模拟 第五章利用发生函数给出了一般二元递归序列的精确公式，并利用渐近计数方法计 算了它们的渐近值 第六章给出了两个生物序列比对个数的精确公式，并且运用多元函数的渐近估计法 研究了它的渐近性 第七章利用发生函数的奇异性分析方法给出了正二项分布和负二项分布的一阶逆矩 的渐近展开，并利用泊松化和去泊松化的方法进一步研究了正二项分布和负二项分布的 r 阶逆矩的渐近性 关键词；组合和式；r i c e 公式；俨交错和；递归序列；序列比对；二项式系数倒数； 发生函数；逆矩；奇异性分析；泊松化和去泊松化；渐近估计 渐近计数方法及其应用 a s y m p t o t i ce n u m e r a t i o nm e t h o d sa n dt h e i r a p p l i c a t i o n s a b s t r a c t i nt h i st h e s i s ，w eg i v ea s y m p t o t i c so fs p e c i a lc o m b i n a t o r i a ls u m s ，t h en u m b e ro fa l i g n m e n t s o fb i o s e q u e n c e sa n di n v e r s em o m e n to fp o s i t i v eb m o m i a la n dn e g a t i v eb i n o m i a lb ya s y m p t o t i c e n u m e r a t i o nm e t h o d s t h em a i nc o n t e n t so ft h i st h e s i sc a r lb es u m m a r i z e da sf o l l o w s ： i nc h a p t e r2 ，w eg i v ep r e c i s ef o r m u l a eo fs p e c i a lc o m b i n a t o r i a ls u m sb yg e n e r a t i n gf u n c t i o n a n df u r t h 日s t u d yt h ea s y m p t o t i e so fc o m b i n a t o r i a ls u i n s ：= 0 ( ：) a n d 翟1 ( ；) 7 古 i nr e c e n ty e a r s ，t h es t u d i e so nt h ei d e n t i t i e si n v o l v i n gt h ei n v e r s eo fb i n o m i a lc o e f f i c i e n t s h a v eg r a d u a l l yi n c r e a s e d ，b u tn o tm a n ys t u d i e so nt h ea s y m p t o t i cb e h a v i o r so ft h es u m m a t i o n o ft h ei n v e r s eo fb i n o m i a lc o e f f i d e m s i nc h a p t e r3 ，w eg e ts o m eo fr e s u l t so ff i n i t es u u l s a n di n f i n i t es e r i e si n v o l v i n gp o w e r sa n di n v e r s eo fb i n o m i a lc o e f f i c i e n t sb ym e a u so fg e n e r a t i n g f u n c t i o n sa n dt h ei n t e g r a lt h e o r y w ea l s om a k el l s eo fa s y m p t o t i ce n u m e r a t i o nm e t h o d st o c o m p u t et h ea s y m p t o t i cv a l u e s hc h a p t e r4 w ee x t e n dr i c e 8l e m m aa n ds t u d yt h ea s y m p t o t i e so ft h ea l t e r n a t i v ec o m - b i n a t o r i a ls u m sb yr i c e sl e m m aa n dr e s i d u et h e o r e ma n dg i v ei t sq - a n a l o g i nc h a p t e r5 ，w eg i v ep r e c i s ef o r m l l l a eo ft h et w o - d i m e n s i o n a lr e c u r s i o ns e q u e n c e sb yg e n - e r a t i n gf u n c t i o na n ds t u d yi t sa s y m p t o t i e sb ya s y m p t o t i ce n u m e r a t i o nm e t h o d s - i nc h a p t e r6 w eg i v ep r e c i s ef o r m u l a eo ft h en m n b e ro fa l i g n m e n t so fb i o s e q u e n c e s ，a n d m a k eu s eo fg e n e r a t i n gf u n c t i o na s y m p t o t i ce s t i m a t i o nt e c h n i q u et oe o m p u t ei t sa s y m p t o t i c v a l u e s i nc h a p t e r7 ，w eg i v ea s y m p t o t i ce x p a n s i o n so f t h ef i r s ti n v e r s em o m e n to f p o s i t i v eb m o m i a l a n d n e g a t i v eb i n o m i a lb ys i n g u l a r i t ya n a l y s i sm e t h o d ，a n df u r t h e rs t u d y t h ea s y m p t o t i e sf o rr - t h i n v e r s em o m e n to fp o s i t i v eb i n o m i a la n dn e g a t i v eb i n o m i a li nt e r m so ft h ep o i s s o n i z a t i o na n d d e p o i s s o n i z a t i o nm e t h o d k e y w o r d s ：c o m b i n a t o r i a ls u m ；r i c e 8f o r m u l a ；q - a r e r n a t i v es u m s ；r e c u r s i o ns e - q u e n c e ；a l i g n m e n t so f s e q u e n c e s ；i n v e r s eb i n o m i a lc o e f f i c i e n t ；g e n e r a t i n gf u n c t i o n ； i n v e r s em o m e n t ；s i n g u l a r i t ya n a l y s i s ；p o i s s o n i z a t i o na n dd e p o i a s o n i z a t i o n ；a s y m p - t o t i ce s t i m a t e s i i 独创性说明 作者郑重声明：本博士学位论文是我个人在导师指导下进行的 研究工作及取得研究成果。尽我所知，除了文中特别加以标注和致 谢的地方外，论文中不包含其他人已经发表或撰写的研究成果，也 不包含为获得大连理工大学或其他单位的学位或证书所使用过的材 料。与我一同工作的同志对本研究所做的贡献均已在论文中做了明 确的说明并表示了谢意。 作者签名：重鲎日期：丝21 ：! j 大连理工大学博士学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解呔连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文 作者签名： 导师签名： 乌丢自靡 拯鲤 大连理工大学博士学位论文 1 绪论 1 1渐近计数方法的背景，理论意义以及应用价值 渐近计数是组合数学的重要研究课题之一_ 般地说，渐近计数提供了组合函数的 增长速率的信息，它回答的典型问题是， ( 1 ) n 元集合分拆的个数随着付如何增大? ( 2 ) 如何比较n 元集合分拆的个数与n 元集合的排列个数? 在组合计数问题中确实存在一些人们所希望的完美无缺的枚举结果例如，如果用 k 表示n 元集合的子集个数，则k = 扩计数问题的解既简明又精确并且关于n 一致成 立它不仅提供了k 的全部的信息并且对任何n 很容易计算然而，在组合计数方法的 应用中，这样的例子是极罕见的通常，即使计数问题的解的表示式存在，它也是十分复 杂的，并且包含和式或递推式因此，我们常常需要了解某个计数问题的解k 当n o 。 时的渐近性状，而渐近式则扬弃了计数问题的解k 的次要部分，突出了它的主要部分， 它使我们能更清楚地了解支配这一表示式的决定性部分，从而对它更好地研究比如， 在算法分析中，我们不仅需要求出一类算法的运算次数k 的表示式，还要进一步研究当 n o o 时k 的增长速率并且要与其他算法进行比较得到最优算法，此时使用渐近式是 菲常必要的另外，有很多计数阿题要求出它的解的精确表示式十分困难或者根本不可 能，在这种情况下，我们往往设法求出它的渐近值例如，和式k = e 2 卸( 警) 没有封闭 形式但是当n o o 时，k 一2 ( 辅又如，设”( n ) 为不超过n 的素数个数，要求出z ) 的精确表示式是不可能的，然而，当n o o 时，z ( n ) 一n l l o g n ，它深刻地反映了素数的 分布规律渐近估计可以确定一个等式是否成立，而且被研究的计数问题的解没有显示 表示式时，也能够处理它们的间接关系渐近方法的目的是，当7 1 - 充分大时，提供能够 描述计数问题解k 增长率的简单而明显的表示式简单性是渐近估计的重要的优点，但 是渐近式过于简单往往减弱了它的准确性，这就需要在简明和精确之间进行协调现在 越来越多的领域，如算法分析，信息论、统计学、计算分子生物学、统计物理学、图论等 学科都广泛地应用渐近计数方法，并且解决了许多实际问题因此该课题具有重要的理 论意义和应用价值 渐近计数方法及其应用 1 2 渐近计数方法的理论和研究概况 渐近计数方法的研究有着悠久的历史，从上世纪五十年代末到九十年代，b e n d e r ， o d l y z k o ，f l a j o l e t ，w i l f ，d eb r u i j n 等著名学者为渐近计数的研究奠定了理论基础 最常用的渐近计数方法为：发生函数方法r i c e 方法，奇异性分析、梅林变换，和式变 换方法、泊松化和去泊松化，拉普拉斯方法等等相应的文献见f 1 - 9 】 组合计数问题中经常出现组合和式，我们遇到组合和式的第一个反应总是验证是否 可以通过某个恒等式来简化它如果关于这个和式没有发现恒等式，下一步，我们应该 试图将问题转换成没有和式的形式通常我们不是对一个孤立简单的和式感兴趣，而是 把它变成一个参数化的族比如k = ，关于求这类和的渐近值，w i l l 3 1 提供了 一个叫历金油”的强有力的方法，用发生函数求组合和式的渐近值 对于由正项组成的和式k = e k ( k ) ，( 七) 0 ，此时( ) 一般含有阶乘因子，且 ( 七) 为单峰的d eb r u i j nf 7 】、b e n d e r 【1 】、屠规彰 6 】、o d l y z k of 2 】等详细讨论了寻求 此种组合和式渐近值的方法，并且先后给出了二项式系数幂的和整数分拆的个数幂的 和b e l l 数、n 元集合映于自身的所有映射的集合的个数的渐近值 m e i n t o s hf 1 0 利用 同样的方法给出了二项式系数幂积的和的渐近值f l a j o l e t 在【4 】中提出了利用奇异性分 析方法处理二项式和的一般框架j a c q u e t 和s z p a n k o w s k i 【9 】用泊松化和去泊松化的方 法研究了二项式和的渐近性，并利用这个方法给出了s h a n n o n 熵和e 陌n y i 熵的完全渐近 展开式 有些计数问题的解k 是由交错项组成的和式h = k ( 一1 ) 2 ( 七) ，( 七) 0 一般 地，由于正负项之间的抵消作用，k 常比各项绝对值之和k ( 七) 要小得多，因而处理 起来要比正项和式的情形困难得多有时我们可以分离正项和负项的和，然后分别估计 它们但是一般情况下我们尽量避免使用这种方法，因为ta ( 2 k ) 与e k ( 2 + 1 ) 常 渐近相等，很难估计其差的渐近式屠规彰在【6 】中，提出了简便的方法，即设法将k 转 换为正项和的情形如果( ) 单调递减，可将和式写成k ( ( 2 ) 一a ( 2 k + 1 ) ) ，此时 若( z ) 为光滑函数，还可用以( 2 ) = 一( 甚( z ) ) 。雏来代替a ( 2 k ) 一a ( 2 k + 1 ) 有些时候，利用发生函数求它的渐近值往往更为简便，但是由交错项和式给出的组合 计数问题的解，通常是由包含排除原理”得来的，很难得到相应的发生函数b e n d e r 在 1 】1 中利用b o n f e r r o n i 不等式给出了在很多情形中能求出渐近值的一般的方法，并使用 这个方法给出了吩放问题”和对子问题”的渐近值d eb r u i j n 【7 】提出把此类和分类 获得调和和，然后通过梅林变换求出它的渐近值f l a j o l e t ，g o u r d o n 和d u m a s 【5 】利用 梅林变换全面系统地研究了调和和的渐近性，并给出了很多应用还有一种比较有效的 方法就是r i c e 方法f 5 】f 1 a j o l e t 和s e d g e w i c k 在【5 】5 中利用r i c e 方法深入研究了有限差分 和的渐近性在算法分析、数据结构分析等研究中经常导出此类和 当组合序列的发生函数给定时，利用发生函数方法是最有效的发生函数方法不仅 有助于寻求计数问题解的显式，而且在渐近计数方面也是一个十分有用的工具，从发生 2 大连理工大学博士学位论文 函数出发通常比直接从和式出发更易得出解的渐近式发生函数为解析函数时，因为解 析函数的奇异点对它们的幂级数系数的渐近行为影响很大，所以针对发生函数的奇异点 的特点可以得到计数问题解的渐近性 对于发生函数的奇异点仅为极点的情形，w i l f 【3 】和o d y z k o 【2 】进行了研究并且取 得了一系列的成果 对于发生函数有代数奇异点的情形，d a r b o u x 【1 1 】给出了收敛圆上具有代数奇点时 函数的渐近展开但d a r b o u x 定理适用于收敛圆上只有一个奇异点的情况，s z e g o 【1 2 把 d a r b o u x 定理推广到有几个这种奇异点的情况j u n g e n 【1 3 推广了d a r b o u x 定理，并研 究了当发生函数具有代数与对数形式的奇异点时系数数列的渐近性态c o m t e t 【1 4 、 g o u l d e n 和j a c k s o n 1 5 】、o m y z k o 1 6 】、f l a j o l e t 和o d l y z k o 【1 7 也得到了一系列研究成 果f l a j o l e t 和o d l y z k o 【1 8 对【1 6 ，1 7 】中的结论进行了更为全面的推广当发生函数的奇 异点很小( 即变化缓慢函数) 时，用f l a j o l e t 和o d l y z k o 【1 8 提出的转移定理最有效 对于发生函数没有任何奇异点，即发生函数为整函数的情况，d eb r u i j n 在m 中研究 了当鞍点不在实轴上鞍点方法的应用e v g r a f o v 【1 9 、w o n g 【2 0 ，o d l y z k o 2 】等人也不 同程度地研究了鞍点方法，并给出了许多应用 k i r o u s i s ，s t a m a t i o u 和v a m v a k a r if 2 1 】用 鞍点方法给出了酽二项式系数的渐近性o d l y z k o 在【2 】中指出当发生函数在它的收敛 圆上有唯一的大奇异点( 即快速增长的函数) 时，用鞍点方法是最有效的但使用鞍点方 法是有限制条件的h a y m a n 在【2 2 】中提出了可用鞍点方法的函数类，并和m o s e r 【2 “叫 研究了第一类和第二类s t i r l i n g 数的渐近性 当发生函数以隐函数形式给出时，h a r a r y 和p a l m e r 【2 5 】给出了行之有效的定理，并 利用它得到了无标号有根树个数的渐近值b e n d e r 【1 】改进了这个定理并利用它给出了 有根及无根无标号二元树的计数问题的渐近值w a t e r m a n h o f a c k e r ，s c h u s t e r 等人 2 a 2 9 利用 1 】1 的定理给出了r n a 二级结构的计数的渐近值廖波和王天明 3 0 ，3 1 】深入 研究和推广了他们的结果m e i r 和m o o n 在【3 2 】中也得到了类似的结果 对于多元发生函数，其系数渐近性的估计比较困难从函数的性质很难看出确定系 数的渐近性的临界区域，并且这些区域很复杂奇异点和零点不像一维的情况那样是孤 立的，而是形成k 个变量的一1 维流形特别是，有理函数情况不容易处理b e r d e r | 3 3 】 利用中心和局部极限定理研究了存在小的奇异点的二元函数的系数的渐近性 b e n d e r 和r i c h m o n 在阻，3 5 】中推广了 3 3 4 的结论并应用到许多有趣的组合问题中 f l a j o l e t 和 s e d g e w i c k 【3 嘲利用同样的思想给出了更一般的结论p e m a n t l e 和w i l s o n 【3 7 ，3 8 4 研究了 多元函数的奇异点是光滑点时系数的渐近性，并利用它给出了一般r i o r d a n 数组的渐近 性【3 9 】 渐近计数方法已经渗透到了各个领域并且其研究至今仍十分活跃渐近计数方法未 来的研究趋势主要是各个领域中的应用由于组合计数问题的多样性和复杂性，针对问 题的不同处理的方法就不同，渐近式的推导方法往往因问题而变，很难纳入几种模式之 3 渐近计数方法及其应用 中，因此我们应该灵活应用渐近计数方法，发挥好它的其他学科不可代替的作用 1 3 论文的主要内容 本文利用渐近计数方法给出了一些特殊组合和式，生物序列的比对个数以及正负二 项分布逆矩的渐近值 本文的主要工作概括如下： 1 在第二章我们利用发生函数方法给出了关于特殊组合和式的恒等式并利用渐近计 数方法讨论了组合幂和式：= 0 ( ；) 和怎。( ：) 击的渐近性 2 近几年，涉及二项式系数倒数的恒等式的研究逐渐增多，但是关于二项式系数倒 数和的渐近性，至今得到的结果并不多本章利用【1 0 】中的定理1 1 ，发生函数方法以及 【1 2 】中的定积分方法建立了一些包含二项式系数倒数以及幂的有限与无限和式并且利用 渐近计数方法给出了它们的渐近值由此，我们得到了与第二类s t i r r i n g 数有关的一些新 的恒等式 3 渐近计数方法已经在许多计算机科学理论中，特别是在算法分析中成功地得到应 用组合计数和算法分析有着密切联系，它们都是处理特殊计数结构的两个领域使用 的方法几乎相同，而且它们也在相互不断地交流和促进在算法分析的许多问题中，经 常导出序列 d 厶= ：l ：。l ( 一1 ) 8 ， ；8 其中，序列a 能扩充为一个解析函数，) 估计此类交错和的最有效的方法是r i c e 方 法本章推广了r i c e 引理【5 】，利用它和留数定理研究了交错组合和的渐近性，并给出了 它们的口- 模拟 4 在第五章利用发生函数给出了在不同的初始条件下一般常系数二元递归序列的精 确公式，并运用渐近估计法研究了它的渐近性 5 生物序列比对是一项很复杂并且具有相当难度的工作两个序列的比对有许许多 多的可能，从中找出最好的比对非常困难因此，这些工作成为数学工作者的不可推卸的 任务比对个数的结果在负面意义上对生物学有用，它肯定了存在巨大数量的对比，并 且直接枚举是没有希望的在第六章，我们给出了两个生物序列比对个数的精确公式， 并运用多元函数的渐近估计法计算了它们的渐近值 6 ，概率分布的逆矩与各种各样的统计应用有关但是，通常很难得到封闭形式，因 此其渐近展开成为研究热点在第七章我们利用发生函数的奇异性分析方法给出了正二 项分布和负二项分布的一阶逆矩的渐近展开此外，我们还利用泊松化和去泊松化的方 法进一步研究了正二项分布和负二项分布的r 阶逆矩的渐近性 4 大连理工大学博士学位论文 1 4 有关渐近分析的记号和概念 定义1 1 【6 设，( n ) 与g ( n ) 为正整数n 的实值函数，则记号 ( 1 ) ，( n ) = o 白( n ) ) 错( n ) xd ( 9 ( 竹) ) 表示存在与竹无关的常数c 与m 使得当 c n 。o 时( n ) m l g ( n ) l 成立 ( 2 ) ，( n ) = 口( 9 ( n ) ) 表示 l i m 螋：0 “一”9 【卅 ( 3 ) ，( 彬一夕( 嘞表示y ( n ) = 9 ( 而( 1 + o ( 1 ) ) ，亦即 l i m 型：l n 叫9 ( n ) 特别地，o ( 1 ) 表示一个趋于零的量，而o ( 1 ) 表示个有界量 0 ，0 ，一的运算； ，( n ) = 0 ( ，( 住) ) ， c o ( f ( n ) ) = 0 ( ，( n ) ) ， o f f ( n ) ) + 0 0 ( n ) ) = d ( ，( n ) + g ( n ) ) ， 0 ( ，( 佗) ) d b ( 礼) ) = d ( ，( n ) g ( n ) ) ， o f f ( 哪夕m ) ) = ，( n ) d 0 ) ) ， ( n ) = d ( g ( n ) ) ，g ( n ) = d ( ( 付) ) = l ( n ) = 0 ( h ( n ) ) ， 其中c 是与n 无关的常数上述诸式除了，( 哪= 0 ( ，( n ) ) 外，对于0 记法同样成立此 外如下运算也成立 使得 d ( ，( n ) ) 0 0 ( n ) ) = o ( ，( n ) 9 ( n ) ) ， ( d ( ，( n ) ) + d b ( n ) ) ) = o f f ( n ) ) + o ( 9 ( n ) ) ( 1 + d ( ，( n ) ) ) ( 1 + d 0 ( n ) ) ) = 1 + o ( ( n ) + g ) ) ， ( n ) 一g ( n ) ，9 ( n ) 一九( 竹) = ( n ) 一h ( n ) 定义1 2 1 6 1 设s 为k 所取值的某一集合，若存在不依赖于n 与k s 的常数c 与m ( ) i m i k ( 女) 5 渐近计数方法及其应用 对所有满足c n o 。，k s 的n 与女均成立，则称。( ) = d ( ) ) 一o o ) 关于是 一致的又若( ) = k ( ) ( 1 + d ( 1 ) ) 一o o ) ，其中隐含在o ( 1 ) 中的常数与k 占的选择 无关，则称o 。( ) 一k ( 后) 关于k s 是一致的 由此定义可得：若( ) = 0 ( h ( 女) ) 关于s 为一致，则必有s ( 后) = o ( e k e sb , , ( k ) ) 同样若( ) 一k ( ) 关于k s 为一致，则k s ( ) 一蚝sk ( ) 6 大连理工大学博士学位论文 2 关于组合和式的渐近展开 我们研究组合计数问题时常常遇到如下形式的组合和式； k = ( 膏) 知 通常，0 k n 或0 k o o 如果我们能找到和式的封闭形式，固然是好但是，有时我们很难得到它的封闭形 式，而且有的即使有封闭形式，也是十分复杂的所以，我们研究它的渐近性是很有必要 的研究组合和式渐近性的最有效的方法是w i l l 3 】的“万金油”方法即，利用0 f i ( ) 的 性质寻找k 的发生函数f ( z ) 的简单形式，然后由( z ) 的性质获得k 的渐近性但何 金油”方法不是万能的，一些组合和式很难求出它的发生函数，此时，我们需要尝试使 用其他方法 。一 如果组合和式k = k ( ) 的通项( 功0 ，关于固定的付，f a 。( 女) 是单峰的，并且? 满足如下三个条件之一； ( 1 ) ( ) + 1 ) ，对于所有的耘 ( 2 ) ( ) - t - 1 ) ，对于所有的砖 ( 3 ) 口，l ( ) + 1 ) ，对于k 粕，并且( ) + 1 ) ，对于k 硒， 那么，可以通过文献f 1 , 2 ，6 ，7 】提出的方法，寻求此种和式的渐近值 一般地，若要求k 的渐近值，通常是找( 知) 的最大值可以通过( ) 的渐近估 计找；如果( 七) 包含阶乘或二项式系数因子，也可观察比率鱼磐挈是否趋于1 如果对所有的，鱼磐掣 1 ，则是条件( 1 ) 成立 如果在求和范围内存在b ，使得+ 1 ) 趋于) ，则显然是条件( 3 ) 成立，并且 当k 趋于时达到最大值 一旦最大值( ) = ) 被确定，就可分析( ) 在k = 硒两侧的增长速度，并 且从中定出对整个和式起决定性作用的部分，即推出“( ) = o ( ( ) ) ，a = 忙： 知一e 加硒+ ) 的估计式最后，通过e u l e r 求和公式或l a p l a c e 方法或积分方法 来估计和式k e a ( ) ，a = 忙：一s 加+ ，当然有时也可尝试直接求和来 7 渐近计数方法及其应用 估计 本章利用上述方法给出了包含二项式系数的幂和的渐近值讨论问题之前，先给出 一些引理 2 1预备知识 引理2 1 4 0 对每个k20 ，k 为整数 参=砖窑一(巩，j j = 器= n ( z ) ， 0 ，z 0 ，a k 是与r 以及b e r n o u l l i 数b 2 k 有关的有理函数 一证明令s ( n ) = e l o ( ：) = 名o g ( n ，) ，设= 蚰，其中n ( o a 1 ) 是连续变 量由( 2 ，2 ) ，( 2 3 ) 式可得 l o g 咖，功= n l o g ( 面吉乒) + ( j ；) 1 。g n + i l o g a l o g a ( 1 0 。一l 0 9 2 口 + r 喜茄与( 卜刍一f 杀) n - 2 k + 。- o ( 站夸) 对于0 j s 口1 一j 1 一致成立 由上式可以看出 恕删) k ( a 。( 1 1 r = g ( 。) ， ( 2 4 ) 并且对于0 6 s n s 】一j 0 ，我们将证明当n o 。时 s ( n ) = 9 ，) ( 1 + o ( e 一轨) ) ，( 2 7 ) 崩a 1 0 大连理工大学博士学位论文 其中a = ：1 2 一e n s i 2 + e ) ，6 是依赖于e 的正常数 设m l = s u p g ( d ) ：i n 一1 2 i2e ，则7 n 1 g ( 1 2 ) ，选择m 2 和m 3 使得 m 1 舰 m 3 g ( 1 2 ) 因为当n 一时( 9 ( n ，m ) ) ：一9 ( 口) 关于0 q 1 一致成立，所以，对于充分大的m 当k 簪a 时，g ( n ，) 竹碍故 即( 2 7 ) 式成立 设 则 从而 其中 鬻k 萼产外刊c 耖 e 卅函g ( n ，) 、嵋“、m 3 一 心) = ”l o g ( 砜 ) + f l 唱口一知呻一0 。 一；蚝2 鲁2 坤b 2 k m ( 驰1 j + f 知矿洲 ：。铷( 。) + 。( a ) + 壹州。) 南，= n 铷( a ) + 1 ( a ) + 抛( 口) 南， 知= 1 咖，舳) = e x p ( “( 。) + ( f 一；) 1 0 9 n + r 苫p 赢b 南+ 。( n 一妒1 ) ) = b e “( 1 + o ( n 一妒1 ) ) ， s ( n ) = b 唧( t 加) ( 1 + o ( 矿耻1 ) ) 如a a = ：1 2 一s k n 1 2 + s ) ， b = 唧( ( ：一；) l o g n + r 耋砸象面刍) 下面我们利用e u l e r - m a c l a u r i n 求和公式估计和式 e x p ( u ( k n ) ) k a 1 1 渐近计数方法及其应用 令u ( d ) = e ( p ( a ) ，_ | l l u n ( 1 2 + 订 e x p ( u ( k n ) ) k = - ( i 2 - o =_v2托exp)出+五1叩2-卅互1injnu 2 -呻2 + s ) 。) = o 中( 乱0 ) ) 出+ i 矿( i 2 一) + i 矿( 1 2 十e ) ， + 荟丽b 2 k ( u ( 2 k - 1 ) 2 删_ u ( 2 k - i ) 2 叫矿蚪1 + 翮1 ( 后竺如制卿k m 鳓一 f 0 2 + e ) = ，e x p ( ( 重肛) ) 如+ 正 j n ( 1 1 2 - e ) 其中 t ：；u ( 1 1 2 一) + ：u ( 1 1 2 + e ) + 拓1 b 2 k ( u ( 2 k - 1 ) ( 1 2 + ) _ u ( 2 k - i ) ( 1 2 一e ) ) n 洲 + 面南( 蔗如刊) u ( 2 p - i ) 岫炉 先估计 ( 1 2 - i - e 扩( 咖) 出：而f e ie , k 1 2 _ 吲问出 j , k 1 2 - e ) ，一e ，” 因为“( 口) 在口= 1 2 处解析，由t a y l o r 定理，当f 口一i 2 f o ) 下面估计t 当佗一0 0 时， n o l 2 + e 岛升1 一吲) 矿- 1 ( z 肛) 如)岛升1 一吲) 矿- 1 ) ( z 肛) 如) j , l ( 1 l l - e ) ：n 1 胁b 2 舛1 一) u ( 扩l ) d o ：d ( n ) = ”胁 1 一) u 防” = d ( n 南鑫 ， 叫 驰 枷w吼 ，随 渐近计数方法及其应用 又当n 一时，“( a ) = n “o ( a ) + 0 ( 1 ) ，则u ( n ) = e x p ( u ( a ) ) = o ( e n u o ( a ) ) 因此，在t 中包 含u ( 1 2 士) 和u 2 k - 1 ( 1 2 士e ) 的项与r ”( 1 1 1 7 2 2 - “e ) ) p ( ( 。n ) ) 如中的首项比较是指数小 从而，当竹_ + m 时 f 7 。 矿? 。：蓑，m 卜州n 加( i 叫2 + e ) 酬咖煳州。一芝州。 故 跏) = r t l - - r 2 少一正磊唧( r 砉孤关与( - 一z 2 。2 1 ) ( - + 。( 竹。1 ) ) = 潞c t + 薹景圳m 其中p 是非负整数，鲰是与r 以及b e r n o u l l i 数b 2 k 有关的有理函数定理2 2 证明完 毕 由足理2 20 - 7 以得到如下推论 推论2 1 当n o o 时， 妻k - - - o 一器2 ， ( ：) 一 意岛， 、。， v ， 其中r 0 ，z 0 推论2 2 当n o o 时， 耋一 其中z 0 推论2 3 当竹一时 o n 、2 ” 荟“南2 ，缸= o 、。， v 。、 ， 其中r 0 用同样的方法，我们可以得到如下定理 定理2 3 对于每个非负整数p ，当n o 。时， 耋( n ) 可1 = 茄c + 妻象+ 。m ，一1 ， 大连理工大学博士学位论文 其中r 0 ，z 1 ，b 是与r 以及b e r n o u l l i 数b 2 k 有关的有理函数 由定理2 3 可以得到如下推论 推论2 4 当n o o 时， 三n 、1 2 n r + l k = l ( 习可“丽2 ， 、， v、， 其中r 0 ，l 1 推论2 5 当n o o 时， 耋( ：) 吉一等， 其中z 1 1 5 大连理工大学博士学位论文 3 关于包含二项式系数倒数和的渐近性 二项式系数在组合分析、图论，数论、统计和概率等许多数学领域内都有重要应用 研究这类组合和式的方法多种多样，并且得到的结果也极其丰富，请参考文献f 7 9 j 近几年，涉及二项式系数倒数的恒等式的研究逐渐增多，并得到t ? g 多重要结论， 参看文献 4 1 4 卑但是关于二项式系数倒数和的渐近性，至今为止得到的结果并不多，例 如文献【1 4 】中有下面的结论； ；塞g ) “，+ 萎n 中1 其中整数满足e p 。b z 一9 p l = ( 2 一e 2 ) 一。 4 2 本章利用【4 3 中的定理1 1 和发生函数方法以及【4 5 】的定积分方法得到了一些包含 二项式系数倒数的和的恒等式，接着利用发生函数渐近计数方法以及直接方法给出了它 们的渐近值由此，我们得到了一些与第二类s t i r l i n g 数有关的恒等式 3 1 预备知识 引理3 1 【删设n 竹2k 是任意非负整数，f ( n ，k ) 定义如下 地砷= 学f 出) q ”- k ( o a t ， 其中p ( t ) 和口( d 是定义在阻1 ，忱】上的两个函数设 ) 畦。和 k ) 。o 是任意两个序 列，并且a 0 ) ，b ( z ) 是其对应的普通发生函数，则 磊匡，( n , k ) a k b n - k z n = 刍pfb ( x q ( t ) d t a ( x p ( t ) ) b ( x q ( t ) d t j 1 f ，(= 专l ，厂 ”0h = 0 一l o “ 4 1 引理3 2 【4 5 】对于非负整数n 和k ， 却+ 1 ) z 1 脚卅“出 1 7 渐近计数方法及其应用 引理3 3 【4 0 0 对每个整数r 0 ，我们有 e 。k r z k 西咖，蒂杀= 翳吲 t jk 0 = o 一7、7 其中s ( r ，j ) 和如 ) 分别是第二类s t i r l i n g 数和e u l e r i a n 多项式 引理3 4 【“】设b k ( y ) 和风分另0 是b e r n o u l l i 多项式和b e r n o u l l i 数，则 引理3 5 【1 4 1 b k ( v ) = 妻k 轧矿 = ( ：) 昂一t 矿 - - - - - - 0 、。7 喜肚再1 厂b “时1 ) - ) 引理3 6 【1 4 ( f r o b e n i u s ) e u l e r i a n 多项式有如下展开式： n 如 ) = z 占，七) p 一1 ) “ 其中s ( r j ) 是第二类s t i f l i n g 数 引理3 7 【1 4 】e u l e r i a n 多项式有如下展开式 其中a ( n ，功是e u l e r i a n 数 引理3 8 【4 6 】 如( z ) = a ( n ，砷矿，山( z ) = 1 薹e 扩= 若特一1 塞g ) 若特c n + 矿一， 其中a k ( 妫是e u l e r i a n 多项式 引理3 9 【4 7 】设r 是任意非负整数，则 其中s (