From the archive, 1

As a result of emptying my office, various old papers have come to light. (Many more interesting papers have no doubt gone into the skip; I had to work fast to meet the deadline.) From time to time I will post bits and pieces here.

The first item in this series concerns a simple argument due to Titus Hilberdink, which in conjunction with a general result about power series gives a short proof of a theorem of Rényi: the limiting probability that a random (labelled) forest on n vertices is connected (as n→∞) is 1/√e.

A general result

Theorem Let f(z) = ∑ anzn have positive radius of convergence r, and assume that an/an+1 → r.

  • Let g(z) be analytic in a circle with centre 0 and radius strictly greater than r. If f(z)g(z) = ∑bnzn, then bn ∼ g(r)an.
  • Suppose that f(z) is convergent at z = r and that f(0) = 0. Let h(z) be analytic in a circle with centre 0 and radius strictly greater than r. If h(f(z)) = ∑cnzn, then cn ∼ h‘(f(r))an.

Multiplication and function composition mirror natural operations on species of combinatorial objects, and this theorem is a very useful tool. I’ll use it just as a black box, and say nothing about the proof. (I hope I got it right!)

Here is a well-known example done this way. A set carrying a permutation can be decomposed uniquely into a set of fixed points and a set carrying a derangement (a fixed-point-free permutation). In terms of the species Set, Perm and Derang of sets, permutations and derangements, we have Perm = Set×Derang. So the same equation holds for the exponential generating functions for labelled objects. These are exp(z) for sets and 1/(1−z) for permutations, so the e.g.f. for derangements is exp(−z)/(1−z). The first part of the theorem immediately implies that the number of derangements is asymptotically exp(−1) times the number of permutations.

The sum of a series

Titus Hilberdink provided me with a short proof of the fact that

∑ nn−2/(n! exp(n)) = 1/2.

Note a curious feature of this series. We are accustomed to an infinite series of rationals with an irrational sum; this is a series of irrationals with rational sum.

The proof uses the fact that the inverse function l(z) to z exp(−z) is the exponential generating function for rooted trees, namely ∑(nn−1 zn)/n!. (This can be proved by Lagrange inversion, or by an argument involving Cauchy’s integral formula.) It follows from Stirling’s formula that this series converges for z = 1/e (and, by a much simpler version of the argument below, its sum is 1). So the series on the left of what we are trying to prove is equal to the integral, from 0 to 1/e, of l(t)/t with respect to t. (Note that the term-by-term integration is justified by the uniform convergence.)

Put t = ueu, so that u = l(t). There is a lot of cancellation, and we are left with integrating 1−u with respect to u between the limits 0 and 1, which gives 1/2 as required.

The conclusion

Let Trees and Forests be the species of trees and forests on a given set. We have the usual relation between connected objects and all objects, namely Forests = Sets[Trees−1]. So the exponential generating function for forests is obtained by substituting that for trees (with the constant term removed) into the exponential function. By the second part of our theorem, we see that, if Tn and Fn are the numbers of trees and forests on an n-set, then

Fn ∼ exp(1/2)Tn,

as required.


About Peter Cameron

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

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 )

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.