Bijective enumeration of some colored permutations given by the product of two long cycles

Let γ n be the permutation on n symbols defined by γ n = ( 1 2 … n ) . We are interested in an enumerative problem on colored permutations, that is permutations β of n in which the numbers from 1 to n are colored with p colors such that two elements in a same cycle have the same color. We show that the proportion of colored permutations such that γ n β − 1 is a long cycle is given by the very simple ratio 1 n − p + 1 . Our proof is bijective and uses combinatorial objects such as partitioned hypermaps and thorn trees. This formula is actually equivalent to the proportionality of the number of long cycles α such that γ n α has m cycles and Stirling numbers of size n + 1 , an unexpected connection previously found by several authors by means of algebraic methods. Moreover, our bijection allows us to refine the latter result with the cycle type of the permutations.