Search

In the symmetric group on a set of size 2n, let denote the conjugacy class of involutions with no fixed points (equivalently, we refer to these as “pairings”, since each disjoint cycle has length 2). Harer and Zagier explicitly determined the distribution of the number of disjoint cycles in the product of a fixed cycle of length 2n and the elements of . Their famous result has been reproved many times, primarily because it can be interpreted as the genus distribution for 2-cell embeddings in an orientable surface, of a graph with a single vertex attached to n loops. In this paper we give a new formula for the cycle distribution when a fixed permutation with two cycles (say the lengths are , where ) is multiplied by the elements of . It can be interpreted as the genus distribution for 2-cell embeddings in an orientable surface, of a graph with two vertices, of degrees p and q. In terms of these graphs, the formula involves a parameter that allows us to specify, separately, the number of edges between the two vertices and the number of loops at each of the vertices. The proof is combinatorial, and uses a new algorithm that we introduce to create all rooted forests containing a given rooted forest. [Copyright &y& Elsevier]

Abstract: 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 , the enumeration of which is equivalent to the Harer–Zagier formula. The elements of are of the form , where is a pairing on , is a partition into k blocks of the same set, and a certain relation holds between and . (The set partitions that can appear in are called “shift-symmetric”, for reasons that are explained in the paper.) The direct bijection for identifies it with a set of objects of the form , where is a pairing on a -subset of (a “partial pairing”), and t is an ordered tree with k vertices. If we specialize to the extreme case when , then is empty, and our bijection reduces to a well-known tree bijection. [Copyright &y& Elsevier]