Enumeration of planar constellations
This paper studies transitive ordered factorizations of a given permutation. For \(n\geq 1\), let \(\sigma_0\in S_n\) be a fixed permutation with \(d_i\) cycles of length \(i\). For \(m\geq 2\), the paper counts the number of ordered \(m\)-tuples of permutations from \(S_n\) that factor \(\sigma_0\), i.e. \(\sigma_0= \sigma_1\sigma_2\cdots\sigma_m\), with the following additional properties: (1) the group generated by \(\sigma_1,\sigma_2,\dots, \sigma_m\) acts transitively on \(\{1,2,\dots, n\}\), and (2) \(\sum^m_{i=0} c(\sigma_i)= n(m- 2)+ 2\), where \(c(\sigma_i)\) denotes the number of cycles of \(\sigma_i\). The number of factorizations satisfying the conditions above is \[ m{[(m-1)n- 1]!\over [(m- 1)n- c(\sigma_0)+ 2]!} \prod_{i\geq 1} \left[i\begin{pmatrix} mi-1\\ i\end{pmatrix}\right]^{d_i}. \] A bijection relates these factorizations to some rooted planar maps. An old result of Hurwitz counting similar factorizations into transpositions yields as a specialization of this result.
ordered factorizations of a given permutation
scientific article; zbMATH DE number 1501934
scientific article