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

Abstract

Let ${\gamma }_n$ be the permutation on $n$ symbols defined by ${\gamma }_n=(12\dot{.}.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.

22 pages. Version 1 is a short version of 12 pages, entitled "Linear coefficients of Kerov's polynomials: bijective proof and refinement of Zagier's result", published in DMTCS proceedings of FPSAC 2010, AN, 713-724