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,k, the enumeration of which is equivalent to the Harer-Zagier formula. The elements of B_p,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 B_p,k are called “shift-symmetric”, for reasons that are explained in the paper.) The direct bijection for B_p,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.