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

Valentin Féray, Ekaterina A. Vassilieva

Published 2010-06-17, updated 2012-11-08Version 2

Let $\gamma_n$ be the permutation on $n$ symbols defined by $\gamma_n = (1\ 2\...\ n)$. We are interested in an enumerative problem on colored permutations, that is permutations $\beta$ 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 $\gamma_n \beta^{-1}$ is a long cycle is given by the very simple ratio $\frac{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 $\alpha$ such that $\gamma_n\alpha$ 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.