COUNTING IN GROUPS : FINE ASYMPTOTIC GEOMETRY
COUNTING IN GROUPS : FINE ASYMPTOTIC GEOMETRY
复制标题
分组计数：精细渐近几何
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
M. Duchin
中科院分区：
文献类型：
--
作者：
M. Duchin
假设我们要研究一个整数序列（an）n∈n，并描述它是如何增长的。一个激励的例子是斐波那契数列1,1,2,3,5，…。，满足著名的递归式an = an−1 + an−2。我们可以应用18世纪的思想（归功于de Moivre，并被欧拉出色地发挥了作用），形成相关的生成函数A(x) =∑∞n=0 anx n∈Q[[x]]，序列的值作为形式幂级数的系数。由递归得到A(x)−xA(x)−xA(x) = 1，得到A(x) = 1 1−x−x2∈Q(x)作为有理函数（多项式的比值）的优美形式。其中一些很容易概括。假设斐波那契式递归是一个整数系数和有限深度的递归：an = α1an−1 +···+ αkan−k。我们再次得到A(x)是一个有理函数，分母是1−α1x−···−αkx。我们说生成函数是有理函数的序列有有理增长。让我们考虑一下这告诉我们关于序列的什么……
Suppose we want to study a sequence of integers (an)n∈N and characterize how it grows. A motivating example is the Fibonacci sequence 1, 1, 2, 3, 5, . . . , which satisfies the famous recursion an = an−1 + an−2. We can apply an 18th-century idea (attributed to de Moivre, and put to excellent effect by Euler) and form the associated generating function A(x) = ∑∞ n=0 anx n ∈ Q[[x]], with the values of the sequence as coefficients in a formal power series. From the recursion, we find that A(x) − xA(x) − xA(x) = 1, obtaining the nice form A(x) = 1 1−x−x2 ∈ Q(x) as a rational function (a ratio of polynomials). Some of this generalizes readily. Let’s say that a Fibonacci-style recursion is one with integer coefficients and finite depth: an = α1an−1 + · · · + αkan−k. We once again get A(x) as a rational function, with denominator 1−α1x−· · ·−αkx. We’ll say that sequences whose generating functions are rational functions have rational growth. Let’s consider what this tells us about the sequence...