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

From MaRDI portal
Revision as of 18:31, 3 July 2023 by Importer (talk | contribs) (‎Created a new Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
Bijective enumeration of some colored permutations given by the product of two long cycles
scientific article

    Statements

    Bijective enumeration of some colored permutations given by the product of two long cycles (English)
    0 references
    0 references
    11 January 2012
    0 references
    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.''
    0 references
    colored permutations
    0 references
    bipartite maps
    0 references
    long cycle factorization
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references