（应用数学专业论文）组合学中的渐近计数方法.pdf

大连理工大学硕士学位论文 摘要 研究组合计数的方法有很多，渐近计数方法是最重要的研究方法之一。本文应用 渐近计数方法研究组合计数问题。 本文的主要工作可概括如下： 在第二章中，我们应用l a p l a c e 方法讨论一些和式的渐近展开，我们给出了涉及广 义调和数和二项式系数的一些和式的渐近值。 在第三章中，我们运用d a r b o u x 方法研究一些特殊数的性质。如：我们讨论了s a l i 6 数 和p 。s t i r l i n g 数的渐近值。 在第四章中，我们先应用系数方法建立了一些与两种广义调和数有关的恒等式。 进一步地，利用奇异性分析方法，求出涉及广义调和数的一些和式的渐近展开。 关键词：s t i f l i n g 数；调和数；c a u d l y 数；发生函数；l a p l a c e 方法；d a r b o u x 方法；奇异 性分析法：渐近展开 组合学中的渐近计数方法 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 s o fc o m b i n a t o r i c s a b s t r a c t t h e r ea x em a n ym e t h o d st os t u d yc o m b i n a t o r i a le n u m e r a t i o n p r o b l e m so fc o m b i n a t o - r i a le n u m e r a t i o n ，a n da s y m p t o t i ce n u m e r a t i o nm e t h o di so i l eo ft h em o s ti m p o r t a n ta p p r o a c h i nt h i st h e s i s ，w ei n v e s t i g a t ep r o b l e m so fc o m b i n a t o r i a le n u m e r a t i o nb ya p p l y i n ga 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 t h em a i nr e s u l t so ft h i st h e s i sc a nb es u m m a r i z ea sf o l l o w s ： i nc h a p t e r2 w ed i s c u s st h ea s y m p t o t i ce x p a n s i o n so fc e r t a i ns u m sb yu s l n gl a p l a c e 7 s m e t h o d w eg i v et h ea s y m p t o t i cv a l u e so fc e r t a i ns u m si n v o l v i n gg e n e r a l i z e dh a r m o n i cn u m b e r s a n db i n o m i a lc o e f f i c i e n t s i nc h a p t e r3 ，w ei n v e s t i g a t et h ep r o p e r t i e so fs o m es p e c i a ln u m b e r sb yd a r b o u x sm e t h o d f o re x a m p l e ，w ed i s c u s st h ea s y m p t o t i ce s t i m a t i o no fs a l i 6n u m b e r sa n dp s t i r l i n gn u m b e r s i nc h a p t e r4 ，w ef i r s te s t a b l i s hs o m en u m b e r si d e n t i t i e sr e l a t e dt ot w ok i n d so fg e n e r a l i z e d h a r m o n i cb yt h em e t h o do fc o e m c i e n t s f u r t h e rm o r e w ec o m p u t et h ea s y m p t o t i ce x p a n s i o no f s u m si n v o l v i n gg e n e r a l i z e dh a r m o n i cn u m b e rb ys i n g u l a r i t ya n a l y s i sm e t h o d k e y w o r d s ：s t i r l i n gn u m b e r s ；h a r m o n i cn u m b e r s ；c a u c h yn u m b e r s ；g e n e r a t i n g f u n c t i o n ；l a p l a c e sm e t h o d ；d a r b o u x sm e t h o d ；s i n g u l a r i t ya n a l y s i sm e t h o d ；a s y m p - t o t i ce x p a n s i o n 独创性说明 所呈交的学位论文，是本人在导师的指导下进行研究工作所取得的成果 尽我所知，除文中已经注明引用内容和致谢的地方外，本论文不包含其他个人 或集体已经发表的研究成果，也不包含其他已申请学位或其他用途使用过的成 果与我一同工作的同志对本研究所做的贡献均已在论文中做了明确的说明并 表示了谢意 若有不实之处，本人愿意承担相关法律责任 学位论文题目：燃臣业丝逝鱼丛塑壶整 作者签名：j 苗丛耻日期：上覃年鱼月_ 二虬日 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 ! 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目：纽鱼鲤鱼垒鱼丛塑墨堕 作者签名：垄避日期：趔 年：兰月z 竺 日 导师签名：j 叁垮日期：斗年月业日 大连理工大学硕士学位论文 1引言 1 1 组合学的研究方法 随着统计学、代数学、数论的发展，特别是电子计算机出现后，诞生于十七世纪 的组合学逐渐显示出在数学理论及应用中其它科学无法替代的作用，如今，组合学渗 透到很多领域，它与其它学科相结合，不断的创造出新的理论及新的方法。同时规划 学、生物数学等学科的发展也为组合数学提供了新问题，总之，随着科学技术的日新 月异，组合数学这个古老的数学分支充满了活力和挑战。 二项式系数、c a u c h y 数、s t i r l i n g 数、调和数、l a h 数等这些特殊数都是组合数学 中非常重要的数，都具有深刻的组合背景，故我们称之为经典组合序列。经典组合数 列，来源于组合数学中的计数问题，并在许多问题中当作计数工具来使用，例如，涉 及有限结构的代数问题在某种程度上都具有组合特征；在计算分子生物学、概率统计 计算和计算机算法的复杂性分析中，经常会遇到各种类型的组合恒等式的计算问题； 在统计物理中，计算系统处于某种特定状态下的几率往往需要求出该系统有多少种可 能的状态；在化学及遗传学中，需要研究分子按一定法则相互结合时可能形成多少种 结构。此外，这些特殊数的重要作用一直是研究的热门话题，许多人已经研究出了很 多经典的结果，它们都具有深刻的意义，已经成为很多问题研究的基础，包括许多离 散问题都与它们有密切的联系。至今对这些问题的研究还是吸引着不少数学工作者的 目光。 组合计数是组合数学的重要研究课题之。研究组合计数的方法很多，常用方法 包括发生函数方法、反演方法、渐近计数方法、超几何级数方法、群论方法、计算机 算法等。而本篇文章着重介绍了渐近计数方法。 1 1 1 渐近计数方法的介绍 1 1 1 1 渐近计数方法的意义及应用价值 在组合计数中，我们常寻求某个计数问题的解，如( 九) 当佗趋于无穷时的渐近性 质，这是因为通常( n ) 的表示式十分复杂，而渐近式则扬弃了问题解次要部分，突出 它的主要部分，它使我们能更清楚地了解支配这一问题解的决定性部分，从而对问题 1 组合学中的渐近计数方法 解有更清楚的了解。如对正二项分布的r 阶逆矩：，以) 矿q n 一，0 0 。一般 地，由于正负项之间的抵消作用，k 常比各项绝对值之和f 。( 忌) 要小得多，因而处理 起来要比正项和式的情况困难得多。 有些时候利用发生函数求它的渐近值往往更为简便，但是有交错项和式给出 的组合计数问题的解，很难得到相应的发生函数。一种比较有效的方法是r i c e 方 2 大连理工大学硕士学位论文 法f 5 。f 1 a j o l e t 和s e d g e w i c l 【在f 5 中利用c e 方法深入研究了有限差分和的渐近性。在算 法分析、数据结构分析等研究中经常导出此类和。 当组合序列的发生函数给定时，利用发生函数方法是最有效的。发生函数方法在 渐近计数方面也是一个十分有用的工具，从发生函数出发通常比直接从和式出发更易 得出解的渐近式。发生函数为解析函数时，因为解析函数的奇异点对它们的幂级数系 数的渐近行为影响很大，所以针对发生函数的奇异点的特点可以得到计数问题解的渐 近性。 对于发生函数有代数奇点的情况，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 e t e t 1 4 、 g o u l d e n 幂i j a c k s o n 1 5 1 、o d l y z k o 1 6 、f l a g o l e t $ 1 0 d l y z k o 1 7 也得到了一系列研究成果。 f l a g o l e t 和o d l y z k o 1 8 对f 1 6 ，17 1 中的结论进行了更为全面的推广。发生函数的奇异点很 小( 即变化缓慢函数1 时，用f l a j o l e t 和o d l y z k o i s 提出的转移定理最有效。 对于发生函数没有任何奇异点，即发生函数为整函数的情况，d eb r u i j n 在f 7 中研 究了当鞍点不在实轴上鞍点方法的应用。e v g r a f o v 1 9 、w o n g 2 0 、o d l v z k o f 2 1 等人也不 同程度的研究了鞍点方法，并给出了许多应用( 如f 2 1 ，f 2 1 1 ) 。h a y m a n 在f 2 2 1 中提出了可用 鞍点方法的函数类，并和m o s e r f 2 3 2 4 1 研究了第一类和第二类s t i r l i n g 数的渐近性。 当发生函数以隐函数给出时，h a r a r y $ 1 p a l m e r 2 5 给出了行之有效的定理，并利用 它得到了无标号有根树个数的渐近值。b e n d e r i 改进了这个定理并利用它给出了无标 号二元树计数问题的渐近值。 在数学的某些分支及其应用中，如果出现含参数的积分，求这类含参数的积分的 渐近值则要用至! u l a p l a c e 方法，即运用l a p l a c e 渐近积分定理解决这类问题。 几种渐近计数各有千秋，适应范围也不同。一般来说，对于组合序列的渐近研 究，从序列的发生函数入手比较容易些； 面l a p l a c e 方法和梅林变换方法是处理大参数 实积分的有效方法；r i c e 方法主要用于研究交错组合和问题；当组合和式的一般项含有 阶乘因子时，通常使用和式变换方法求其渐近值，奇异性分析方法可用于处理二项式 和问题：泊松化及去泊松化主要用于研究概率问题。由于某些组合和式可转化为大参 数积分的计算，由此可用l a p l a c e 方法。我们在应用渐近方法研究组合问题时，应根据 问题的性质，选择合适的渐近计数方法。 本篇论文的主要内容：在第二章中，我们应用l a p l a c e 方法讨论一些和式的渐近 展开，我们给出了一些关于广义调和数和二项式系数的一些和式的渐近值。在第三章 中，我们运用d a r b o u x 方法研究一些特殊数的性质，比如讨论t s a l i 百数和p s t i r l i n g 数的 渐近值。在第四章中，我们先应用系数方法建立了一些与两种广义调和数有关的恒等 式。然后，利用奇异性分析方法，得出涉及广义调和数的一些和式的渐近展开。 3 组合学中的渐近计数方法 1 1 2 发生函数的定义及表示 定义l 。1设给定一实数或复数序列，f 本文中这些序列常常由具有组合意义的正 整数组成) ，则把下列三个形式级数西，皿，和西q 。 圣( 亡) = 俨， 礼0 皿( t ) = 磊， 札2 u 西q ( 亡) = 口n t 竹， ( 其中q n 是给定的序列) 分别称为序列。礼的普通发生函数，指数发生函数和更一般的关 于的发生函数。 有定义可知发生函数主要分为两种：设是一序列f 1 4 1 ， 令f ( z ) = 7 b - ：- oa n x n ，则称，( z ) 为序y u a 竹的普通幂级数发生函数，特别适应于做出 涉及组合数的序列的发生函数； 令f ( x ) = 甚oa n 等，则称j p ( 。) 为序列n 钆指数型发生函数。特别适应于做出涉及排 列的序列的发生函数； 此外还有一种发生函数，如令厂( z ) = 甚。帮，则称，( z ) 为序列o n 的d i r c b l e t 级数， 在乘法数论中，d i r c h l e t 级数是常用的发生函数。 1 2 s t i r l i n g 数的定义及发生函数 忌一划分数s ( 礼，后) ( 划分成屉个块) 1 4 ，称为第二类s t i r l i n g 数，因此s ( 佗，k ) 0 ，s ( 礼，k ) = 0 ，1 佗k 。其中s ( o ，0 ) = 1 ，s ( o ，k ) = 0 ，k21 。换句话说，s ( u ，忍) 是上有忌个等， 价类的等价关系的数目，也就是钆个不同的球分配到尼个不加区别的盒子中( 合子顺序不 考虑) 使没有盒子是空的分配的个数。 第二类s t i r l i n g 数s ( n ，尼) 有“垂直”的发生函数为： 薹跗习t n = 掣舱。 第一类s t i r l i n g 数的“垂直 发生函数为： 如等= 扣 大连理工大学硕士学位论文 1 3 记号及概念 1 3 1 系数 妒】，( t ) 表示厂( t ) 的形式幂级数， ) = 甚。厶俨中俨的系数，即 陆n 】厂( t ) = 厶， 故陋n 】被称为求系数的操作函数。 妒 无论是在解决组合问题还是在渐近计数中都是非常重要的，我们通过系数问题 可以发现很多幂级数的性质。当为非负整数时，用厂( 亡) 和夕( 亡) 表示两个幂级数，妒 满 足 3 3 】： 1 3 2 二项式系数 护 ( 厂 ) + p 9 ) ) = q 陋n 】， ) + p 陋竹】夕 ) ， 旺n t 厂( t ) = t - - 1 厂( 亡) ， 妒i f 协) = ( 礼+ 1 ) i t n + l 】厂( 亡) ， r t 旧弛) 夕( 亡) = ( m ) ) 旷砖龇) ( 1 1 ) ( 1 2 ) ( 1 3 ) ( 1 4 ) 二项式系数是组合序列的基础，在概率统计、数论中有广泛的应用。二项式系数 的定义( 二) 的组合意义是： 1 3 30 关系和记号 ( 三) = 寿篙 设厂( z ) 和( 。) 是实数集合x 上的函数，c 是x 的极限点( c 可以是+ o 。或一o o ) 。若z x 且z c 时，f 描l 是有界的，则记 f ( x ) = d ( ( z ) ) ( z _ c ，z x ) 特别当l 船i 在x 上有界时，则记 f ( x ) = o ( ( z ) ) ( z x ) 5 组合学中的渐近计数方法 o 关系有如下运算性质 4 2 ： ( 1 ) f = o ( 夕) ，( x _ c ，z x ) g a o ，则有i f l 口= o ( 1 9 l a ) ，( z _ c ，x x ) ( 2 ) 若 = 0 ( 玑) ， _ c ，z x ) ，且锄是常数，则有 叱五= o ( f q t l l g i l ) ( x _ c ，z x ) i = 1t = 1 ( 3 ) 若五= o ( g t ) ， _ c ，z x ) ，则有 n = o ( n 吼) ，( z c ，z x ) = 1 若存在正常数m ，仇使得当x x 且xjc 时有 。 m f 器f m 悯 则说o 关系t 厂( z ) = ) ( z _ c ，z x ) 是最佳的。有时说当z _ c 时l 厂( z ) 与( z ) 时弱等价 的，记作 ，( z ) ； 多( z ) ( z c ，z x ) 特别记，当z c 时有 磐器= 2 0 ， 则记t 厂( z ) = 万( ( z ) ) _ c ，z x ) ，明显地，若厂( z ) = 石( ( z ) ) ( z c ，z x ) ，则 有，( z ) x 咖( z ) ( z c ，z x ) ， 1 3 40 关系和记号 设- 厂 ) 和矽( z ) 是实数集合x 上的函数，若z x 且z _ c 时，有 l i r n 咖f ( ( z x i ) = 。， 则记 f ( x ) = d ( ( z ) ) ( 2 _ c ，。x ) ， 明显地，o 关系是一种特殊的o 关系 4 2 】。 有定义不难列出0 记号的一些简单等式： 大连理工大学硕士学位论文 ，( 佗) = 0 ( 厂( 仃) ) ， c 0 ( 厂( n ) ) = 0 ( 厂) ) ， d ( 厂( 钆) ) + d ( 9 ( 礼) ) = p ( ，( 佗) + 夕( 死) ) ， 0 ( o ( 厂( 佗) ) ) = o ( i 厂( 佗) ) ， o f f ( n ) ) o ( g ( n ) ) = p ( 厂( 扎) g ( 扎) ) ， 0 ( 厂( 佗) 夕( 佗) ) = 厂( 钇) 0 ( 9 ( 住) ) ， f ( n ) = d ( 夕( 死) ) ，9 ( 扎) = o ( 九( 佗) ) 号，( 佗) = d ( 九( 咒) ) 其中式中c 为与礼无关的常数。上述诸式除去厂( 佗) = d ( 厂( 佗) ) 外，对于d 记法同样成立。 此外还成立 d ( 厂( 扎) ) d ( 夕( 佗) ) = o ( ，( 佗) 9 ( n ) ) ， ( d ( 厂( 扎) ) + d ( 夕( n ) ) ) 知= o ( 厂( 礼) 七) + d ( 夕( 佗) 知) ， ( 1 + d ( 厂( 佗) ) ) ( 1 + o ( 夕( n ) ) ) = 1 + d ( ，( 礼) - i - - 9 ( 扎) ) ， 厂( 佗) 一9 ( 礼) ，9 ( 钆) 一h ( n ) 净l 厂( 他) 一九( 钆) 等等。 1 3 5 渐近等价关系和记号 设，( z ) 和砂( z ) 是实数集合x 上的函数，c 是x 的极限点，若z x ，且z _ c 时，有 l i m l x - - + c 锱| - l ， 回【zl 则说当z c 时，( z ) 和 ) 是渐近等价的，记作 厂( z ) 一砂( z ) ( x _ c ，z x ) ， 明显地渐近等价关系也是一种特殊的万关系 4 2 】。 渐近等价关系也可以写作厂 ) 一( z ) ( z _ c ，z x ) 可以写作如下形式： y ( x ) = ( z ) + d ( ( z ) ) ( x _ c ，z x ) 7 大连理工大学硕士学位论文 2 l a p l a c e 渐近方法 在分析学的某些分支及其应用中，经常出现如下形式的含参数积分 厂6 j ( a ) = j f ( z ，a ) d x 口 并需要在确定当a 一0 ( 3 时，了( a ) 的渐近值，通常称这类问题为大参数积分的渐近计 算。 1 9 世纪法国数学家p s l a p l a c e 在概率解析理论一书中，由于研究大数事件概 率的需要，首先提出研究如下形式积分的渐近值： p i ( n ) = ( z ) 胪( z ) 】n d x ，口 其中n 是大整数，在相当一般的条件下，他找到当佗_ o 。时，( 礼) 的渐近公式，并给出 这个公式在计算某些大参数函数方面的应用。 l a p l a c e 方法4 2 1 是解决大参数积分渐近值的主要方法，该方法的核心是l a p l a c e 渐 近积分定理。实际上，l a p l a c e 渐近积分定理是一个局部化定理，也就是说，该定理的 核心不过是表明积分j ( 仡) = e ( z ) 厂( z 炉d x ，f ( x ) = e h ( z ) 的渐近性完全由，( z ) 在取有效 最大值位置z = 的邻域内的积分决定，换言之，在点任意小邻域上的积分完全决定了 整个，( 纯) 的渐近状态。在本章中，我们将详细介绍l a p l a c e 渐近积分定理的内容。 2 1 l a p l a c e 定理 在介绍l a p l a c e 渐近积分定理之前先介绍有效最大值的概念。 定义2 1 ( 有效最大值) 设厂( z ) 是区间a ，6 】上的实值函数，称厂扛) 在( a ，6 ) 处取得有效最大值是指对每一 个不包含的区间a ，c 】和陋，6 】( c 善 d ) ，在其上函数厂( z ) 的上确界小于厂 ) ，即 m a x ( s u p ，( z ) ，s u p ，( z ) ) ，( ) $ f a ，c 】z e d ，6 】 对无穷区间上函数的有效最大值概念可以类似的给出。 9 组合学中的渐近计数方法 引理2 1 ( l a p l a c e 渐近积分定理) 设( z ) ，九( z ) 及，( z ) = e h ( ) 是定义在有限或无穷区间( a ，6 上的函数，且适合如下条 件： ( a ) ( z ) p ( z ) 在a ，6 】上绝对可积，( 扎) ( b ) 危( z ) 在内点( a ，6 ) 达到有效最大值，且允( z ) 在点邻域具有二阶连续导数和 7 ( ) = 0 ， ”( ) 1)_na0)ln o + n 1 4 - + r 。1 像p a s c a l - - - ：角阵一样，广义调和数也可以用三角阵的形式表示，它t 约r i o r d a n 阵表示， 已有很多研究者研究过。其中广义调和数日( 礼，r ) 的发生函数定义为( 见 27 】) ： 妻跏肚幽竿型 ( 2 1 ) 1 0 大连理工大学硕士学位论文 由上式两边对t 积分然后整理又可得如下发生函数： ( 2 2 ) 调和数在数论和组合学中有重要的作用，对它的研究有非常重要的葸义。 c 加w a y 和g u y 把广义调和数破】定义为超调和数，它是由反复重复调和数的部分 和所得到的。 令麟1 = o ，r o ，礼0 ，磁= 1 n ，当r ，礼1 ，时 础= 趔卜1 1 ，础1 = 玩 g o n w a y 和g u y 4 4 把超调和数表示为如下： 础= ( 佗j 二j1 ) 一如) ， 它的发生函数定义为： 圣o o 嘞礼= 岽宁 二项式系数( 二) 的倒数与一个定积分之间存在如下关系： ( 三) 一1 = ( 佗+ 1 ) z 1 亡m ( 1 一亡) n m 出 ( 2 3 ) 现在我们应用l a 科a c e 渐近积分定理研究广义调和数的性质，同时还计算一些涉及 二项式系数的和式的渐近值。 2 1 1 关于广义调和数的结果 本节应用公式( 2 3 ) 及l 印l a c 澌近积分定理研究超调和数础及广义调和数日( 礼，r ) 的 性质。 定理2 1设7 1 ，当r o 。时 薹础毒希仲瓣一钙 一 警 卅 组合学中的渐近计数方法 证明已知二项式系数与定积分有如下关系： ( 三) 一1 = c 佗+ 1 ，1 z m c l 一z ，n m d 名 因为o t 1 ，即o t ( 1 一t ) j ，所以( t ( 1 一亡) ) n 收敛，故有 n - ：l 列南 = n - - - - - 1 砖1 o 矿( 1 - t ) n 出 。o n ：l 列( 亡( 1 一右) ) 竹如 = j 广。昔1 等t ( 1 铲妃 一 ( 一一亡) ) r k 令，( 亡) = 乍赤鬲，妒( 芒) = l n ( 1 一亡( 1 一亡) ) ，令f 7 ( ) = o 可得= 互1 ，由此可以求得厂( ) = 鲁，垆 ) = i ni ，“( ) = 一詈 0 ，由引理2 1 可得： 因此定理得到证明。 耋础击南 m 瓣) r + 如- ) ( 3 扩4 一 钙 定理2 2设? - 1 ，当r _ o o 时 n 三o o ，聊，毒褊卟矿弋2 1 2 ( 1 n 5 ) 件2 大连理工大学硕士学位论文 证明因为： n 妻。聊，蔷精 = 竹霎跏) ( - 矿f 0 1tnl ”矿出 r l = r + ：1 妻 “0f 霉r + 1日( 仃，r ) ( ( 一艺) ( 1 一古) ) “出 = z 1 螋等紫茅型 十驴机0 1 踏群 - ， lt “1 一 出 令，( 芒) = l n ( 1 + 亡( 1 一亡) ) ，( 亡) = 百西1 习，n = r + 1 ，令，7 ( 毒) = o 可得= j 则：，( 亭) = z 佗i ， ( ) = i 4 ，厂”( f ) = 乎，由l 印l a c e 渐近定理可得： 定理2 3设r2 证明 1 当r _ o 。时， o o 日( v ) n - - - 一r + 1 吆5 ) 什2 ( r 一。) ( 2 礼+ 1 ) ( 蛩) ( n + 1 ) f z - n = r + 1 0 0 ：r 厶 n 一- - - r + 1 = f o r e 一。o o 掣糌逖班 = z 1 志( - 1 ) 7 鲤掣出 ：f i f1翌1们-差-l-lr+22t ( 1 t 出，r 一) 一 1 3 组合学中的渐近计数方法 令厂( 亡) = 2 礼南，( 亡) = 币习1，礼= r + 2 则令厂( ) = o ，可得= ，i 厂( ) = 2 佗l ，矽( ) = 4 ， f “( ) = 一，所以可得： 2 1 2与二项式系数有关的一些和式的渐近值 为了后面叙述的方便，先介绍两个公式： 定理2 4令 当忌_ 0 0 时有： 证明 壹n - ：- o ( 竹玲n =( 1 一u ) 七+ 1 竹( 钆：七) 矿_ 粤豢 鼠= 薹者拣， 疋= 薹o o 等黯 鼠。( 要) m 2 j 乱i 1 ， u i 1 死 ( - 矿( 一扩尼辱 当川 1 时，甚。扩( 1 一z ) n 收敛可得： ( n ：尼) z 1 z nc 1 一z ，乱d z = 1 薹( 礼玲叫n 如 = t 1 一x ( x z ) p “ 1 4 脚 脚 = & 大连理工大学硕士学位论文 令，( 。) = 丽1 ，妒( z ) = 1 ，则： ，7 ( z ) = 1 2 x 1 一x ( 1 一z ) 2 厂( 加坐箐暑拶 由，7 ( ) = o 可得= 1 2 ，则厂( ) = 4 3 ，- 厂”( ) = 一萨2 5 ，妒( f ) = 1 则由l a p l a c e 定理可得： ：p 乩。j o 1 一x ( 1 一z ) 卜“ 同理可以证得死一( - 1 ) 七( 一詈) 惫十m 定理2 5已知 则当k _ o 。时有： 证明已知发生函数： a 七= b 置= 。r 兰1 七+ 2 、3 7 虽( n ：七)r 翌 鲁死( 警) 耋锩笋 小2 c 扩归辱 鼠一( 1 ) 知2 ( 一詈) m 2 耋学壮知南叫咖l n 已知当 l 时，罢1 矿( 1 一z ) n 收敛，故有 伽三薹( 佗：七) z 1 硼_ 如 南薹( 佗挣c 1 _ 圳n 11 ， 而矿i 丌币如 1 5 厮 组合学中的渐近计数方法 由l a p l a c e 定理令厂( z ) = f 不1 习，矽( z ) j 4 ，” ) = 一蒡，矽 ) = 4 ，则 同理可以证得鼠的渐近。 推论2 1 = 而习1 ，由，7 ( ) 一( 1 一z ) 田， 小2 c 扩胆屠 = o 可得= ，故可得厂( ) = 一 已知定理2 5 中定义的a ，当忌_ 。时，有 a k + l - - a 一( 吾) 3 2 证明已知 a 豇+ ，一a 七= 三1 i 蛐l a p l a c e 定理n - - i 以证得结论成立。 定理2 6 当忌一。o 时，有下式成立： 证明 1 一z ( 1一z ) p 1 西2 ( e 1 4 1 ) 槲2 = 薹端n t ( 1 j 厂o m 叫m 惫 一1 ) r 卜叫p 。 = 去z 1 南薹等 盟 亡( 1 一t ) n 如 = 筹石1 志玎1 e t ( 1 _ t ) _ 1 舳， 2 百上石习乏! 、 ) 僦， 由l a p i a c e 定理可得：令厂( 亡) = e t ( 1 - t ) 一l ，妒( 芒) 矗与则可得 ，( 亡) = ( 1 2 t ) e ( 1 一， ，”( t ) = 一2 e 。( 1 一+ ( 1 2 艺) 2 e 。( 1 一扪 当- 厂7 ( ) = o 时，= 考，妒( ) = 4 厂( ) = e 1 4 1 ，厂“( ) = 一2 e 1 4 0 则可得 一两2 ( e 1 4 1 ) m 2 1 6 唑噼 双磊 础 唑噼 双磊 1 | 忍丽n迎州 廊 大连理工大学硕士学位论文 定理2 7 成立。 证明证明同上。 一( e l 4 1 ) 七十1 2 1 7 丽竹 、，一 砧一d 一+ s 一凯 时 一州 r =慨1 | 一 当 大连理工大学硕士学位论文 3d a r b o u x 方法 对于发生函数有代数奇点的情况，我们用d a r b o u x 方法来解决。 3 1d a r b o u x 定理 在了解d a r b o u x 方法之前，我们首先介绍一下代数奇点的定义。 定义3 1 ( 代数奇点) 若函数，( z ) 有奇点q ，在其邻近夕( z ) 可以写成( 1 - 虬z o o 的形式，其中9 ( z ) 在及的邻近解 析且异于零，叫为正实数，则称及为厂( z ) 的u 阶代数奇点。 在，( 2 ) 仅有代数奇点时，运用下面介的d a r b o u x 定理，在很多场合可以引出口仃的 渐近性态。 定理3 1 ( d a r b o m 淀理) 喧e f ( t ) = 甚oa 礼t n 在 7 内解析，在= r 上有有限 个代数奇点，设它们中间具有最高阶u 的奇点为q 1 0 l 2 o l m ，则 一篙( 妻一庇- - n k = lo k ( a 惫) a + 0 ( r 1 ) ， o n2 丽( 乙 庇+ o ( r ”) ) 其中r ) 为g a 1 m a 函数，鲰( 亡) 为与奇点q l c 相应的函数9 ( 芒) ，亦即 肌( 口七) = 。一l i m a ( 1 一毒) 坝啦 本章将应用d 甜b o u x 定理研究s a l i 6 数$ 1 p s t i r l i n 9 数的性质，我们先介绍s a h 6 和p s t i f l i n g 数的定义。 s a l i 6 1 4 整数岛n 的发生函数为： 峥等2 & 竹南 并且存在整数爱礼使岛n ：2 n 爱行，爱n ：( 一1 ) ( ) ( r o o d4 ) 1 9 e u l e r 序列b 的发生函数为： 组合学中的渐近计数方法 其中e o = 1 ，易= 1 ，e 4 = 5 ，e s = 1 3 8 5 ，e 1 0 = 5 0 5 2 1 由上面的定义可得e 2 n 和岛n 满足下列关系： & n 2 莩2 n ) e 2 “ 令口= ( a o ，a 1 ，n 他，) 表示一个无穷的实数列，第二类s t i r h g 数的发生函数可 以表示为如下形式1 4 6 ( 礼，尼) 的另一种发生函数表示为： 薹跏儿f 丽若备可面 很多著作已经研究了鼠( 礼，七) 的性质，但是其中有两个比较有趣的性质容易被忽视掉， 就是对任意的整鳓o ，当= 矿或者= ( n 絮_ 1 ) 时，我们可以得到： 岛( 礼，七，p ) x n = z 惫 兜( 佗，忌，v ) x n = z 七 我们就称& ( 礼，忌，p ) ( 蕾= 1 ，2 ) 为p s t i f l i n g 数。 3 1 1d a r b o u x 定理的应用 定理3 2 s a l i 6 整数& 礼定义为： 皿f 亡) ：c o s h t ： 、7 c o s t 则可得： 1 1 一i v x ) ) ， ( 1 一g ) z ) ) 一弓；( e 弓+ e 一毒) ( 三) 一2 馆 2 0 国 鱼 脚 七 0 z 岛佗 n 脚 l i 一 o zo zo z屉佗& n 脚 = n z 七冰嚣 1|8础 生驯 & 。i 堕刎一，f 大连理工大学硕士学位论文 证明已知 c o s ht 2 ( c o s ht ) e 缸 1 + e 2 i t 在 7 r 内解析，在= 7 r 上有代数奇点乜1 = 三，q 2 = 一争阶数u = 1 同理可求得 故由d a r b o u x 定理可得： g l ( a 1 ) 2 t l 。i m 三( 1 = l i m r 扣考、 7 r 喜) 2 2 t 2 e i tc o s h t 1 + e 2 i t 2 e i tc o s h t 1 + 麓oe 刑与擎 三( e 考+ e 一考) 7 1 9 2 ( q 2 ) = 要( e 三+ e 一暑) ， 南= + e - 弧护+ 弦+ e - 钡一妒+ d ( 扩n = 妻( e 考+ e 一考) 【( 三) 一2 n + ( 一三) 一2 n 】+ 。( ( 三) 一2 n ) = 等( e 三+ e 一至) ( 三) 一2 竹+ 。c c 三，一2 n ， 由( 3 1 ) 式可得： 虹 ( 2 n ) ! 垒i 翌= n l ( 2 n - - 2 ) 当礼_ o 。时， 定理3 3 发生函数为： 丽岛磊 2 礼( 2 竹一1 ) 岛t l 一2 f 至1 2 、2 7 ( 3 1 ) ( 3 2 ) ( 3 3 ) ( p s t i r l i n g s k ) 4 a = ( n o ，口1 ，o n ，) 是无穷的实数列，& ，忌) 的 则有下式成立： & ( 几，k ) x 竹= n = k & ( n ，k ) = ( 1 一a o x ) ( 1 一a l x ) ( 1 一a k x ) a k ( o 惫一a o ) ( a k a k 一1 ) 2 1 ( ( 主三) 一竹+ 。( ( 主三) 一竹) ) 荤 丝一 一 1 一丌 m 磅 h 卜 器弗 组合学中的渐近计数方法 证明 设a k = m n z i o o i ，1 0 1 l ，i 口知l ，记 g a ，知( z ) = & ( n ，k ) x n ， n = k 则g 口，知( z ) 在h 上a k 内解析，在蚓= 壶上有一阶奇点， 所以： 每1 一去) 叫垆 & ( 扎，忍) = a k ( a k a o ) ( 钒一a k 一1 ) a k ( a k 一印) ( 口知一a k 一1 )( ( 毫) 一n + 。( ( 主：) 一n ) ) 引理3 1 g 知s o ( n ，七) 的发生函数，特别的，令知= 1 ，a 1 = 2 ，n 知= k 则可得 第二类s t i r l i n g 数s ( 佗，尼) ( k 固定) 的发生函数： o 。 s ( 竹，忌) 矿= n = k 由d a r b o u x 定理可得： ( 1 一z ) ( 1 2 z ) ( 1 一七z ) 跏等 证明 已知第二类s t i r l i n g 数的发生函数， 析，在= 丢上有一阶奇点q = 昙，而 所以 又因为 所以有 h m n - o o 由d 盯b o u x 定理可得g k ( t ) 在 o 其中s ( n ，歹) 为第一类s t i r l i n g 数，s ( j ，k ) 为第- - 类s t i r l i n g 数。l a h 数的发生函数为： 4 1 一些重要结果 妻k 鲁= 百( - t ) k ( 1 刊七厶，七磊= 百( 1 + 亡) 七 4 1 1 部分特殊数与调和数的关系 c a u c h y 数在渐近中起到很重要的作用，c a u c h y 数和调和