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 10−n.
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.
- Permutations with no consecutive elements
- Asymptotic behavior via generating functions
- Gluons, quarks, envelopes, and letters
- Rates of convergence (this post)