Skip to Main content Skip to Navigation
Conference papers

Arc-Coloured Permutations

Abstract : The equidistribution of many crossing and nesting statistics exists in several combinatorial objects like matchings, set partitions, permutations, and embedded labelled graphs. The involutions switching nesting and crossing numbers for set partitions given by Krattenthaler, also by Chen, Deng, Du, Stanley, and Yan, and for permutations given by Burrill, Mishna, and Post involved passing through tableau-like objects. Recently, Chen and Guo for matchings, and Marberg for set partitions extended the result to coloured arc annotated diagrams. We prove that symmetric joint distribution continues to hold for arc-coloured permutations. As in Marberg's recent work, but through a different interpretation, we also conclude that the ordinary generating functions for all j-noncrossing, k-nonnesting, r-coloured permutations according to size n are rational functions. We use the interpretation to automate the generation of these rational series for both noncrossing and nonnesting coloured set partitions and permutations. otherlanguage*french L'équidistribution de plusieurs statistiques décrites en termes d'emboitements et de chevauchements d'arcs s'observes dans plusieurs familles d'objects combinatoires, tels que les couplages, partitions d'ensembles, permutations et graphes étiquetés. L'involution échangeant le nombre d'emboitements et de chevauchements dans les partitions d'ensemble due à Krattenthaler, et aussi Chen, Deng, Du, Stanley et Yan, et l'involution similaire dans les permutations due à Burrill, Mishna et Post, requièrent d'utiliser des objets de type tableaux. Récemment, Chen et Guo pour les couplages, et Marberg pour les partitions d'ensembles, ont étendu ces résultats au cas de diagrammes arc-annotés coloriés. Nous démontrons que la propriété d'équidistribution s'observe est aussi vraie dans le cas de permutations aux arcs coloriés. Tout comme dans le travail résent de Marberg, mais via un autre chemin, nous montrons que les séries génératrices ordinaires des permutations r-coloriées ayant au plus j chevauchements et k emboitements, comptées selon la taille n, sont des fonctions rationnelles. Nous décrivons aussi des algorithmes permettant de calculer ces fonctions rationnelles pour les partitions d'ensembles et les permutations coloriées sans emboitement ou sans chevauchement. otherlanguage*
Document type :
Conference papers
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/hal-01229660
Contributor : Alain Monteil <>
Submitted on : Tuesday, November 17, 2015 - 10:19:27 AM
Last modification on : Friday, December 18, 2020 - 5:12:01 PM
Long-term archiving on: : Thursday, February 18, 2016 - 11:32:17 AM

File

dmAS0163.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01229660, version 1

Collections

Citation

Lily Yen. Arc-Coloured Permutations. 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), 2013, Paris, France. pp.743-754. ⟨hal-01229660⟩

Share

Metrics

Record views

60

Files downloads

949