Crossings and nestings for arc-coloured permutations and automation

MaRDI QIDQ490316zbMATH OpenFDO

Authors Lily Yen

Publication date 22 January 2015

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1211.3472, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p14

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

arc-coloured permutationautomationbijectioncrossingenumerationfinite state automatongenerating treenestingtableautransfer matrix

Mathematics Subject Classification ID

Partitions of sets (05A18) Combinatorial identities, bijective combinatorics (05A19)

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.

Review text

Summary: Symmetric joint distribution between crossings and nestings was established in several combinatorial objects. Recently, Marberg extended Chen and Guo's result on coloured matchings to coloured set partitions following a multi-dimensional generalization of the bijection and enumerative methods from Chen, Deng, Du, Stanley, and Yan. We complete the study for arc-coloured permutations by establishing symmetric joint distribution for crossings and nestings and by showing that the ordinary generating functions for \(j\)-noncrossing, \(k\)-nonnesting, \(r\)-coloured permutations according to size \(n\) are rational functions. Finally, we automate the generation of these rational functions and analyse the first \(70\) series.

Recommendations

• Arc-coloured permutations
• On k-crossings and k-nestings of permutations
• Crossings and nestings in colored set partitions
• On the complexity of crossings in permutations
• Arc permutations (extended abstract)
• Graph Drawing
• Crossings and alignments of permutations
• scientific article; zbMATH DE number 4101209
• Crossings and nestings of matchings and partitions
• Crossings, colorings, and cliques

Cites work

• \(k\)-noncrossing and \(k\)-nonnesting graphs and fillings of Ferrers diagrams
• Boltzmann Samplers for the Random Generation of Combinatorial Structures
• Combinatorics of genome rearrangements.
• Crossings and alignments of permutations
• Crossings and nestings for arc-coloured permutations and automation
• Crossings and nestings in colored set partitions
• Crossings and nestings in set partitions of classical types
• Crossings and nestings of matchings and partitions
• Growth diagrams, and increasing and decreasing chains in fillings of Ferrers shapes
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• Longest increasing subsequences of random colored permutations
• More bijective Catalan combinatorics on permutations and on signed permutations
• On k-crossings and k-nestings of permutations
• On the page number of RNA secondary structures with pseudoknots
• Oscillating rim hook tableaux and colored matchings
• Standard Young tableaux of height 4 and 5
• Symmetric distribution of crossings and nestings in permutations of type \(B\)

Cited in

(6)

• An algebraic approach to the analytic bootstrap
• Crossings and nestings in colored set partitions
• \(n\)-Rainbow archetypal permutations and strings
• Crossings and nestings for arc-coloured permutations and automation
• 2-colored archetypal permutations and strings of degree n
• Arc-coloured permutations

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Crossings and nestings for arc-coloured permutations and automation

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