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 Bp,k, the enumeration of which is equivalent to the Harer-Zagier formula. The elements of Bp,k are of the form (µ, π), where µ is a pairing on {1,...,2p}, π is a partition into k blocks of the same set, and a certain relation holds between µ and π. (The set partitions π that can appear in Bp,k are called "shift-symmetric", for reasons that are explained in the paper.) The direct bijection for Bp,k identifies it with a set of objects of the form (ρ, t), where ρ is a pairing on a 2(p - k + 1)-subset of {1, ..., 2p} (a "partial pairing"), and t is an ordered tree with k vertices. If we specialize to the extreme case when p = k - 1, then ρ is empty, and our bijection reduces to a well-known tree bijection.