Bijective enumeration of some colored permutations given by the product of two long cycles (Q658051): Difference between revisions

Where the disjoint cycle representation of a permutation consists of just one cycle, that cycle is \textit{long}. Let \(p,n\) \((p\leq n)\) be given integers. A \textit{coloured permutation} is a couple \((\beta,\phi)\) where \(\beta\) is a permutation of \(1,2,\dots,n\), and \(\phi:\{1,2,\dots,n\} \to C\) is a surjection mapping all elements of the same cycle of \(\beta\) to the same element of a set \(C\) of ``colours''; \({\mathcal{C}}(p,n)\) denotes the set of coloured permutations of \(n\) with \(p\) colours, up to bijections on \(C\). \({\mathcal{C}}(\lambda)\) denotes the set of all coloured permutations inducing the same unordered partition \(\lambda\) of \(\{1,2,\dots n\}\). The main result is Theorem 1.4: Let \(p\leq n\) be two positive integers. Fix an integer partition \(\lambda\) of size \(n\) and length \(p\). Choose randomly (with uniform probability) a coloured permutation \((\beta,\phi)\) in \({\mathcal{C}}(\lambda)\). Then the probability for \((\begin{matrix}1&2&\dots&n\end{matrix})\,\,\beta^{-1}\) to be a long cycle is exactly \(\frac{1}{n-p+1}\). From the authors' abstract: ``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.''