Derangements, 1

A classical problem asks: if n letters are put into n addressed envelopes at random, what is the probability that no letter is correctly addressed?

In other words, what is the probability that a random element of the symmetric group Sn is a derangement, that is, has no fixed points?

A standard piece of combinatorics shows that the answer is very close to 1/e, where e is the base of natural logarithms. In fact is the Taylor series for ex, truncated to the xn term, and with −1 substituted for x.

All this is part of something more general. In a previous post on this topic, I mentioned the theorem of Jordan which says that any transitive permutation group of degree n contains a derangement if n>1, and its quantification by Arjeh Cohen and me to the statement that the proportion of derangements in such a group is at least 1/n, with equality if and only if the group is sharply 2-transitive.

I want to discuss first a theorem of seven authors, the alphabetically first being Nigel Boston, which enables us to calculate the proportion of derangements in terms of other data about the group. This has a generalisation to what I call the Shift Theorem which gives the cycle index of the group (a multivariate polynomial which has the proportion of derangements as a specialisation) in a similar form and easily implies the theorem of Boston et al. This theorem holds for certain infinite permutation groups as well (the so-called oligomorphic permutation groups), but we lose the interetation of its specialisation as the proportion of derangements. This raises the question of what these curious numbers attached to various groups actually mean.

Given a permutation group G on the set {1,…,n}, we define two generating functions associated with G as follows:

  • the probability generating function P(x) for the number of fixed points, the polynomial where the coefficient of xi is the proportion of elements of G which have exactly i fixed points (so that the proportion of derangements is P(0));
  • the exponential generating function F(x) for the number of orbits on tuples of distinct elements, the polynomial in which the coefficient of x is the number of orbits on i-tuples of distinct elements divided by i! .

Now the theorem of Boston et al. states:

F(x) = P(x+1).

In particular, we see that the proportion of derangements is F(−1). If G is the symmetric group Sn, then the number of orbits on i-tuples is 1 for 0≤in (and 0 otherwise), so that F(x) is the truncated exponential series, and the result about derangements follows.

Here is the multivariate generalisation. The cycle index of a permutation group G is the multivariate generating function for the proportions of elements of each cycle type: that is, the coefficient of a monomial s1as2b… is the proportion of elements having a fixed points, b 2-cycles, …

The modified cycle index is obtained as follows. Choose representatives for the orbits of the group G acting on the subsets of {1,…,n} (including the empty set and the whole set). For each orbit representative A, take the cycle index of the group G(A) consisting of permutations induced on A by its setwise stabiliser in G. Now sum all thes cycle indices; the result is the modified cycle index.

For example, take G to be the symmetric group S3. The
cycle index of G is (s13+2s3+3s1s2)/6. The modified cycle index of G is the sum of the cycle indices of S0 (which is 1), S1 (s1), S2 ((s12+s2)/2), and S3 (given above).

Now the Shift Theorem asserts:

The modified cycle index is obtained by substituting si+1 for si, for all i, into the ordinary cycle index.

This is easily verified for the above example.

If we substitute si=1 for all i>1, we obtain the generating function P(s1) for fixed points. On the other hand, if we substitute si=0 for all i>1, we obtain 1/|G|, since only the identity contributes. Using this it is easy to see that the theorem of Boston et al. follows from the Shift Theorem.

There is no sensible way to define cycle index of an infinite permutation group. The modified cycle index, however, is more promising. We restrict the sum to orbit representatives of the group acting on finite subsets of its domain. There are infinitely many orbit representatives, but if the group has only finitely many orbits on sets of each given finite cardinality, then the sum makes sense, since each monomial can occur in only finitely many summands. Permutation groups with this finiteness property are called oligomorphic. Thus, the oligomorphic groups are precisely those for which the modifieid cycle index makes sense.

In particular, there is no way to extend the definition of P(x) to infinite groups; but the definition of F(x) makes sense for any oligomorphic group. Here are two examples:

  • Let G be the infinite symmetric group. Then G has just one orbit on i-tuples for all i; so F(x)=ex.
  • Let G be the group of all order-preserving permutations of the rational numbers. There is just one orbit on subsets of size i, but i! orbits on i-tuples. So F(x) = 1+x+x2+x3+… = 1/(1-x).

Putting x=−1, we obtain e−1 for the symmetric group and 1/2 for the group of order-preserving permutations.

What do these numbers mean? (There is no natural measure on either group which makes the probability of a random element being a derangement equal to the appropriate number.)

I think this post is already over-long, but I have more to say about derangements; this will follow sometime.

Previous | Next


About Peter Cameron

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

3 Responses to Derangements, 1

  1. Pingback: On a theorem of Jordan « Peter Cameron's Blog

  2. rjlipton says:

    This is an beautiful piece of work. I really like it and will have to understand the details. Thanks.

  3. Pingback: Derangements, 2 « Peter Cameron's Blog

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