Tuesday, March 18, 2025

Rates of convergence

Computer scienceRates of convergence


The last several posts have looked at counting two kinds of permutations: those that leave no consecutive integers and those that leave no integer fixed. As n grows large, the proportion of permutations of n elements that fall into both classes approaches 1/e. This post will look a little closer and as how fast each proportion approaches 1/e.

(Incidentally, if you’re looking for an problem to explore, take any statement of the form “X converges to Y” and ask how does X converge to Y. Several of the posts on this blog follow that pattern.)

Definitions

To review our definitions, Q(n) is the number of permutations p of 1, 2, 3, …, n + 1 such that there are no consecutive integers, i.e. for no k does p(k + 1) = p(k) + 1. So, for example, 13254 counts, but 15423 does not count because 2 and 3 are consecutive.

Let D(n) be the number of derangements of 1, 2, 3, …, n, i.e. permutations p such that for no k does p(k) = k. So, for example, 23451 counts, but 21354 does not because 3 remains fixed.

Note that Q(n) counts a certain kind of permutation of n + 1 elements and D(n) counts a certain kind of permutation of n elements. This is a little awkward, but I chose my definition of Q to match OEIS. In order to count the proportion of permutations of n elements with no consecutive elements we should look at  Q(n − 1)/n!. Both Q(n − 1)/n! and D(n)/n! converge to 1/e, but not at the same rate.

D convergence

The convergence of D(n)/n! to 1/e is very fast. In fact,

D(n) = [n! / e]

where [x] is x rounded to the nearest integer. So the difference between D(n)/n! and 1/e is less than 0.5/n!. For n greater than or equal to 18, D(n)/n! = 1/e within the limits of floating point precision. As a rule of thumb, you can see about three significant figures in a plot, so for n greater than about 6 you can’t see the difference between D(n)/n! and 1/e.

Q convergence

The convergence of Q(n − 1)/n! to 1/e is leisurely by comparison.

Here’s why. In this post I showed Q(n − 1) is asymptotic to (n + 1)(n − 1)! / e.

So it is true that Q(n − 1)/n! is asymptotic to 1/e, but it is more accurate to say that it is asymptotic to (n + 1) / ne.

D and Q convergence

If we look at the ratio of (n + 1) Q(n) / n to n! then it converges to 1/e about as fast as the ratio of D(n) to n! does.

Said another way,

(n + 1) Q(n) / n ~ D(n)

The ratio of (n + 1) Q(n) / n to D(n) converges to 1 very quickly, with an error on the order of 10n.

On to something else

I intend to end the series here. My next post will probably be about something else, something less mathematical.

So here’s the complete series.

Check out our other content

Check out other tags:

Most Popular Articles