Example using a generating function to find asymptotic behavior

The previous post looked at how to compute Q(n), the number of permutations of 1, 2, 3, …, n + 1 that contain no consecutive integers. We found a way to numerically compute Q(n) but no analytic expression that would let us compute asymptotics.

The sequence Q(n) is sequence A000255 in OEIS, and OEIS gives the exponential generating function of Q:

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

We can use this function and Theorem 5.2.1 from [1] to get the asymptotic form of Q(n). According to that theorem, the coefficient of xn in our generating function is asymptotically the same as the coefficient of xn in the principle part at the singularity at 1. This principle part is

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

and so the coefficient of xn is (n + 2)/e.

So

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

and Q(n) / (n + 1)! approaches 1/e for large n, as conjectured in the previous post.

[1] Herbert S. Wilf. Generatingfunctionology. Second edition.

One thought on “Example using a generating function to find asymptotic behavior

  1. Another way to see the asymptotic behavior of Q(n) is to consider the inclusion-exclusion formula applied similarly to derangements. I think it’s helpful to first consider an “intermediate” problem of counting C(n), the number of permutations of {1,2,…,n} with no consecutive elements… but where we also prohibit the “cyclic” succession (n,1). Then there are n subsets of prohibited permutations, the intersection of any k of which has cardinality (n-k)!, just like derangements… except for the intersection of all n subsets, which is empty.

    So the formula for C(n) looks just like the alternating sum for D(n), just without the final (-1)^n term, and so C(n)/n! has the same asymptotic behavior approaching 1/e.

    Coming back to Q(n), we can take a similar approach, but noting that there are only n prohibited subsets instead of n+1, the intersection of any k of which has cardinality (n+1-k)!.

Comments are closed.