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)
You might be interested in the paper “Unseparated pairs and fixed points in random permutations” by Diaconis, Evans and Graham. They look at the number of k such that p(k+1) = p(k)+1 when p is a uniform partition. They show that this random variable is approximately Poisson distributed with parameter 1. Arxiv version here: https://arxiv.org/abs/1308.5459
I read with great pleasure your series about counting the two kinds of permutations.
Several days ago I thought about the sequence that jams both properties, I mean the number of permutations of a sequence of length n such that there are no fixed points, and no term is next to a term it was next to originally (or, technically speaking, they have only nontrivial intervals)
Fortunately I found the OEIS sequence https://oeis.org/A288208 (let’s call T(n)) and even a nice argument explaining why the ratio n!/T(n) ~ e³
My problem is that I tried to find a closed form expression for that sequence, and I found none, do you have any idea about that?
My two posts on MSE and MO about thar
https://math.stackexchange.com/questions/5039488/closed-form-expression-for-a288208
https://mathoverflow.net/questions/488706/closed-form-expression-for-the-enumeration-of-permutations-with-no-fixed-points