形式陈述
设 是主导奇点公理库主导奇点Dominant singularity · Dominant singularities of a generating function位于生成函数收敛圆上的最近复奇点,其位置与局部类型共同控制系数主要增长。。一个以 为尖点的 -域可写为
其中 、。它在 向外的射线附近挖去一个楔形,使围道能够从收敛圆外侧逼近奇点而不穿过支割。若 能解析延拓到这样的区域,并在其中具有局部展开
则奇点分析用Cauchy 系数积分公理库Cauchy 积分定理与公式Cauchy integral theorem · Cauchy integral formula全纯函数在可缩闭路上的积分为零,并可由边界积分重建内部值与所有导数。把每个标准项转成系数项。对
基本尺度为
余项也必须满足相应的 -域界,才能把误差传递到系数;只有沿实轴的局部等价通常不够。
直觉
方法的核心是把 Cauchy 圆变形成围住主导奇点的钥匙孔轮廓。远离奇点的轮廓段因模更大而指数较小,主要积分集中在离 约 的邻域。缩放 后,局部幂变成 Hankel 积分,而 正是那条积分的常数。
-域不是技术装饰。它提供从奇点两侧绕行的空间,并排除函数在紧贴主导点外侧藏有额外奇点。若只知道 时的实数渐近,复平面其他方向的剧烈行为仍可能改变系数。
例子与边界
Catalan 生成函数
在 附近令 ,有
奇异项是 。由于
转移得到
与 Catalan 数的 Stirling 渐近一致。常数、指数尺度和 都从局部展开逐项得到。
展开中的 与 都是 的一次多项式,对 不再贡献系数;真正控制尾部的是首个非整数幂 。若所谓“正则项”只在局部解析、却不能继续越过其他主导点,则仍须保留它的全局影响,不能仅凭外观看起来光滑就删去。
若 是非正整数, 有极点,而 是多项式并最终没有系数;不能把 当成普遍主项而忽略可能存在的对数因子。形如 的项需要专门的对数转移公式。
若圆周上有多个主导奇点,应分别建立局部展开并把贡献相加;周期性会产生根单位振荡。若函数具有本性奇点、自然边界,或主要贡献来自随 移动的点,则应改用鞍点法公理库鞍点法Saddle-point method · Method of steepest descent选择穿过相位驻点的系数积分轮廓,以局部高斯积分提取主项并控制远离驻点部分的渐近方法。、圆法或其他工具。
推论与应用
解析组合的转移定理公理库解析组合学的转移定理Transfer theorem in analytic combinatorics · Flajolet–Odlyzko transfer theorem在 Δ 解析延拓与余项控制下,把生成函数的局部幂对数奇性转成带精确常数的系数渐近。把标准幂—对数尺度及其误差界整理成可重复使用的规则。结合符号方法,代数型树规格常产生平方根奇点和通用的 行为;对数奇点常对应循环,极点则常对应有限状态或有理结构。
完整工作流是:先定位全部主导点,再证明 -解析延拓,求局部展开,最后逐项转移并控制余项。任一步缺失都可能得到正确外形却错误常数,或在周期剩余类上给出根本不成立的统一渐近。
参考资料
- Philippe Flajolet and Andrew Odlyzko, “Singularity analysis of generating functions,” SIAM Journal on Discrete Mathematics 3(2), 1990, pp. 216–240。
- Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009, Chapter VI。
- Peter Henrici, Applied and Computational Complex Analysis, Vol. 2, Wiley, 1977, Chapter 11, coefficient asymptotics。