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

DOI10.1016/J.DISC.2011.09.010MaRDI QIDQ658051zbMATH OpenOpenAlexWikidataFDO

Authors Valentin Féray, Ekaterina A. Vassilieva

Publication date 11 January 2012

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1006.3474

zbMATH Keywords

bipartite mapscolored permutationslong cycle factorization

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Planar graphs; geometric and topological aspects of graph theory (05C10) Enumeration in graph theory (05C30) Permutation groups (20B99)

Abstract: Let $gamm{a}_n$ be the permutation on $n$ symbols defined by $gamm{a}_n=(\mathrm{12...}n)$. We are interested in an enumerative problem on colored permutations, that is permutations $$ 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 $$ is a long cycle is given by the very simple ratio $frac1n-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 $gamm{a}_{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.

Review text

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.

Recommendations

• scientific article; zbMATH DE number 6750761
• On products of long cycles: short cycle dependence and separation probabilities
• Combinatorially refine a Zagier-Stanley result on products of permutations
• Two enumerative results on cycles of permutations
• Long cycle factorizations: bijective computation in the general case

Cites work

• A bijective proof of Jackson's formula for the number of factorizations of a cycle
• A direct bijection for the Harer-Zagier formula
• An analog of the Harer-Zagier formula for unicellular bicolored maps
• An analogue of the Harer-Zagier formula for unicellular maps on general surfaces
• Annular embeddings of permutations for arbitrary genus
• Factoring \(n\)-cycles and counting maps of given genus
• scientific article; zbMATH DE number 6909301 (Why is no real title available?)
• scientific article; zbMATH DE number 3766017 (Why is no real title available?)
• scientific article; zbMATH DE number 3489159 (Why is no real title available?)
• scientific article; zbMATH DE number 474668 (Why is no real title available?)
• scientific article; zbMATH DE number 1974576 (Why is no real title available?)
• scientific article; zbMATH DE number 919921 (Why is no real title available?)
• scientific article; zbMATH DE number 3298598 (Why is no real title available?)
• Irreducible symmetric group characters of rectangular shape.
• Nombre de représentations d'une permutation comme produit de deux cycles de longueurs données
• Stanley's formula for characters of the symmetric group.
• Two enumerative results on cycles of permutations

Cited in

(5)

• Combinatorially refine a Zagier-Stanley result on products of permutations
• A versatile combinatorial approach of studying products of long cycles in symmetric groups
• On products of permutations with the most uncontaminated cycles by designated labels
• The Harer-Zagier and Jackson formulas and new results for one-face bipartite maps
• On products of long cycles: short cycle dependence and separation probabilities

This page was built for publication: Bijective enumeration of some colored permutations given by the product of two long cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q658051)