Derangements, 2

In the preceding post, I was rather cavalier: I said that if

F(x) = 1+x+x2+x3+… = 1/(1-x),


F(−1) = 1−1+1−1+… = 1/2.

Of course, I am in good company here; this particular piece of chicanery is due to Euler.

What is really going on here is that there are many summation methods for attaching a value to the sum of a divergent infinite series. What we require of any summation method is that, if applied to a convergent series, it should give the correct answer for its sum; and it would be nice if different summation methods, which happen to be applicable to the same divergent series, give the same answer.

Two methods which apply to the above series are

  • analytic continuation, i.e. summing the series in its region of convergence to get an analytic function there, and continuing this function to a larger domain (this is implicitly what I did above); and
  • taking the average of the first n partial sums, and if this has a limit as n→∞, defining this limit to be the sum. (In the example, the partial sums are alternately 1 and 0 and the average does tend to 1/2.)

This will be relevant to another question about derangements, which I will come back to after discussing another example.

The example I want to consider, which I will call S(n,k) for want of a better name, is defined to be the symmetric group Sn acting on the set of k-element subsets of {1,…,n}. We can assume that 1≤kn/2, since the actions on k-sets and (n−k)-sets are isomorphic. I am interested in what happens for fixed k as n→∞. There is also an obvious infinite analogue, the infinite symmetric group acting on the set of k-element subsets of its domain.

For k=1, we have the classical derangement problem in the symmetric group; we saw in the preceding post that there is a formula for the number of derangements in Sn, and that the proportion tends (very rapidly) to 1/e as n→∞. In fact, since the exponential series for negative arguments has alternating signs, the proportion in Sn is alternatively greater than and less than its limit.

The general class is important for several reasons, among them the fact that among primitive actions of the symmetric group, these are the only ones in which the proportion of derangements is bounded away from zero, in a sense made more precise in a paper of Persi Diaconis, Jason Fulman and Robert Guralnick, which contains great richness besides. (In this case, I suspect that a much stronger result holds: it should be rare for a family of primitive groups to have the proportion of derangements bounded away from 0.)

But down to business. Just a little more than was included in the previous post on derangements shows that, for fixed k, the numbers of cycles of length 1,2,…,k in the symmetric group tend to independent Poisson random variables with parameters 1,1/2,…,1/k as the degree increases. This enables us to prove that the limiting proportion of derangements in S(n,k) tends to a limit as n tends to infinity, with fixed k, and (in principle) to calculate this limit.

For example, take k=2. A permutation fixes no 2-set if and only if it has at most one fixed point and no 2-cycle. The limiting probabilities of these two events are (1+1)e-1 and e-1/2 respectively, and they are independent in the limit; so the proportion of derangements in S(n,2) tends to 2e-3/2.

Calculation is not so straightforward for larger k. For example, what are the conditions on a permutation which ensure no fixed 6-set? It can have 5-cycles as long as it has no fixed points; it can have 4-cycles as long as it has no 2-cycles and at most one fixed point; it can have at most one 3-cycle, but only if there are fewer than three fixed points, and there does not exist a fixed point and a 2-cycle. And so on. The result can be computed by Möbius inversion over the poset of partitions of an integer somewhat bigger than k. So I know that the limit exists, but know very little about its properties.

A sample question, to which I don’t know the answer, is:

Let a(k) be the limiting probability, as n→∞, that a random element of S(n,k) is a derangement. Is it true that a(k) is an increasing function of k which tends to 1 as k→∞?

But back to the convergence questions. I will stick to the group S(n,2) (the symmetric group Sn acting on 2-sets). There is an obvious infinite “limit” group in this case, namely the infinite symmetric group acting on 2-sets. Moreover, as already explained, the proportion of derangements tends to the limit 2e-3/2.

What about the numbers of orbits on i-tuples, the other side of the theorem of Boston et al.? In fact, there is a very strong form of convergence for these; for fixed i, they increase until n=2i, and then remain constant. This is because we are counting graphs with i labelled edges (and no isolated vertices), and such a graph can have at most 2i vertices. (I note in passing that the asymptotics of these numbers were recently worked out by Thomas Prellberg, Dudley Stark and me.)

So we have two completely different forms of convergence. Let Fn(x) be the exponential generating function for orbits on tuples of the group S(n,2), and let F(x) be the analogous series for the infinite group. Then we have:

  • The polynomials Fn(x) converge “coefficient-wise” to F(x), in the sense that the coefficient of xi is the same in F(x) as in Fn(x) as long as n≥2i.
  • The values Fn(−1) converge to 2e-3/2.
  • On the other hand, the power series F(x) has radius of convergence 0.

So the problem is:

Make sense of this. In particular, is there a summation method which produces the result 2e-3/2 when applied to the alternating series F(−1)?



About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition, open problems. Bookmark the permalink.

3 Responses to Derangements, 2

  1. Pingback: Derangements, 1 « Peter Cameron's Blog

  2. mwildon says:

    John Britnell and I did a bit of work on this problem a few years ago. We wondered if maybe

    S(n,k-1) \le S(n,k)

    for all n and all k such that 1 < k < n. Obviously, this would imply that the limiting probability a(k) is an increasing function of k. However, after collecting some numerical data we found several counterexamples. The first was

    S(30,9) = 0.61548 > S(30,10) = 0.61452.

    We also used the methods of the Diaconis, Fulman and Guralnick paper to compute a(k) for 1 \le k \le 23. In this range, it is increasing.

  3. See here for Vikraman Arvind’s simple solution to the problem of finding a derangement in a transitive group in polynomial time.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s