使用生成函数寻找渐近行为的示例

上一篇文章介绍了如何计算Q ( n )，即不包含连续整数的 1, 2, 3, …, n + 1 的排列数。我们找到了一种数值计算Q ( n ) 的方法，但没有可以让我们计算渐近的解析表达式。

序列Q ( n ) 是 OEIS 中的序列 A000255，OEIS 给出Q的指数生成函数：

$\sum_{n=0}^\infty \frac{Q(n)}{n!} = \frac{\exp(-x)}{(1-x)^2}$

我们可以使用这个函数和[1]中的定理5.2.1得到Q ( n )的渐近形式。根据该定理，我们的生成函数中的x ⁿ系数与奇点为 1 处的主部分中的x ⁿ系数渐近相同。该主部分为

$\frac{1}{e(1-x)^2} + \frac{1}{e(1-x)} = \frac{1}{e}\left(2 + 3x + 4x^2 + 5x^3 + \cdots\right)$

因此x ⁿ的系数为 ( n + 2)/ e 。

所以

$Q(n) \sim \frac{n + 2}{e} n!$

和Q ( n ) / ( n + 1)！正如上一篇文章中推测的那样，对于大n ，接近 1/ e 。

[1] 赫伯特·S·威尔夫。生成功能学。第二版。