Skip to Main content Skip to Navigation
Journal articles

Factorisations of large cycles in the symmetric group

Dominique Poulalhon Gilles Schaeffer 1 
1 ADAGE - Applying discrete algorithms to genomics
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : The factorizations of an $n$-cycle of the symmetric group $\Sn$ into $m$ permutations with prescribed cycle types $\a_1,\ldots,\a_m$ describe topological equivalence classes of one pole meromorphic functions on Riemann surfaces. This is one of the motivations for a vast literature on counting such factorizations. Their number, denoted by $c^{(n)}_{\a_1,\ldots,\a_m}$, is also known as a connection coefficient of the center of the algebra of the symmetric group, whose multiplicative structure it describes. The relation to Riemann surfaces induces the definition of a \emph{genus} for factorizations. It turns out that this genus is fully determined by the cycle types $\a_1,\ldots,\a_m$, and that it has a determinant influence on the complexity of computing connection coefficients. In this article, a new formula for $c^{(n)}_{\a_1,\ldots,\a_m}$ is given, that makes this influence of the genus explicit. Moreover, our formula is cancellation--free, thus contrasting with known formulae in terms of characters of the symmetric group. This feature allows us to derive non trivial asymptotic estimates. Our results rely on combining classical methods of the theory of characters of the symmetric group with a combinatorial approach that was first introduced in the much simpler case $m=2$ by Goupil and Schaeffer.
Document type :
Journal articles
Complete list of metadata
Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Tuesday, September 26, 2006 - 2:53:00 PM
Last modification on : Friday, February 4, 2022 - 3:30:52 AM


  • HAL Id : inria-00100937, version 1



Dominique Poulalhon, Gilles Schaeffer. Factorisations of large cycles in the symmetric group. Discrete Mathematics, Elsevier, 2002, 254 (1-3), pp.433-458. ⟨inria-00100937⟩



Record views