A direct bijection for the Harer-Zagier formula

We give a combinatorial proof of Harer and Zagier's formula for the disjoint cycle distribution of a long cycle multiplied by an involution with no fixed points, in the symmetric group on a set of even cardinality. The main result of this paper is a direct bijection of a set B-p,B-k, the enumeration of which is equivalent to the Harer-Zagier formula. The elements of B-p,B-k are of the form (mu, pi), where mu is a pairing on {1,..., 2p} pi is a partition into k blocks of the same set, and a certain relation holds between mu and pi. (The set partitions pi that can appear in B-p,B-k are called shift-symmetric, for reasons that are explained in the paper.) The direct bijection for B-p,B-k identifies it with a set of objects of the form (rho, t), where rho is a pairing on a 2 (p - k + 1) -subset of [ 1,..., 2p I (a partial pairing), and t is an ordered tree with k vertices. If we specialize to the extreme case when p = k - 1, then rho is empty, and our bijection reduces to a well-known tree bijection. (c) 2005 Elsevier Inc. All rights reserved.