Asymptotic enumeration, reinforcement, and effective limit theory

渐近枚举、强化和有效极限理论

• 批准号: 0603821
• 负责人: Robin Pemantle
• 金额: $ 20.7万
• 依托单位: University of Pennsylvania
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-05-01 至 2009-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0603821&HistoricalAwards=false
• 关键词: Asymptotic; enumeration; reinforcement; effective; limit

Let F be a multivariate generating function for an array{a_r r in Z^d} of numbers of interest. In the univariate(d=1) case broadly applicable methods are known for obtainingestimates of a_r from the univariate generating function.In the mutlivariate case, no general method is known forextracting asymptotics of a_r from F. The PI has been workingon this with various collaborators since 1998, along the followinglines: use the Cauchy integral formula to write a_r as an integral;use topological and geometric methods to reduce part of thisintegral to a residue computation; use saddle point methodson the remining integral to find an asymptotic expression for a_r.The research proposed here will extend the class of functions F forwhich we are able to compute asymptotics for the coefficients a_r.A second component of the research is to provide algorithmicmeans for doing the computations.The ultimate goal of this work is to facilitate computation.Suppose an array of numbers is described by a recursion; forexample, suppose each one is the sum of all the ones immediatley below and to the left. When the definition is recursive, computing one of the numbers may require computing each of theones before, and there is no evident way to jump in and computesay the 1,000,000th entry. The research in this proposal concernsa way to do just that: to compute an entry arbitrarily far outin the sequence or array without having to compute each intervening entry. These computations are approximate but theyare fast. Moreover, they can be automated, and in fact a partof the proposal is to write software that will perform all thenecessary computations.

设F是一个多元生成函数，它是一个数组{a_r r in Z^d}的一个感兴趣的数。 在单变量（d=1）情况下，从单变量母函数中得到a_r的估计的方法是已知的，而在多变量情况下，从F中提取a_r的渐近性的一般方法是未知的。 自1998年以来，PI一直在与各种合作者一起研究这一问题，沿着以下路线：使用柯西积分公式将a_r写成积分;使用拓扑和几何方法将该积分的一部分化为留数计算;用鞍点法求出了复积分的渐近表达式。r.本文的研究将扩展我们能够计算系数a_r的渐近性的函数类F。r.研究的第二个组成部分是提供进行计算的算法手段。这项工作的最终目标是方便计算。假设一个数数组由一个递归;例如，假设每一个都是紧挨着左下角的所有数的和。 当定义是递归的时候，计算其中一个数字可能需要计算之前的每一个数字，并且没有明显的方法可以跳进去计算第1,000,000个条目。 这个提案中的研究关注的是一种方法：计算序列或数组中任意远的条目，而不必计算每个中间条目。 这些计算是近似的，但它们很快。 此外，它们可以自动化，事实上，该提案的一部分是编写软件来执行所有必要的计算。