(2+2)-free posets, ascent sequences and pattern avoiding permutations

DOI10.1016/J.JCTA.2009.12.007zbMATH Open1225.05026DBLPjournals/jct/Bousquet-MelouCDK10arXiv0806.0666OpenAlexW2121947368WikidataQ60692211 ScholiaQ60692211MaRDI QIDQ986124FDOQ986124

Authors: Mireille Bousquet-Mélou, Anders Claesson, Mark Dukes, Sergey Kitaev 

Publication date: 11 August 2010

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Abstract: We present bijections between four classes of combinatorial objects. Two of them, the class of unlabeled (2+2)-free posets and a certain class of involutions (or chord diagrams), already appeared in the literature, but were apparently not known to be equinumerous. We present a direct bijection between them. The third class is a family of permutations defined in terms of a new type of pattern. An attractive property of these patterns is that, like classical patterns, they are closed under the action of $D_8$, the symmetry group of the square. The fourth class is formed by certain integer sequences, called ascent sequences, which have a simple recursive structure and are shown to encode (2+2)-free posets and permutations. Our bijections preserve numerous statistics. We determine the generating function of these classes of objects, thus recovering a non-D-finite series obtained by Zagier for the class of chord diagrams. Finally, we characterize the ascent sequences that correspond to permutations avoiding the barred pattern $$ and use this to enumerate those permutations, thereby settling a conjecture of Pudwell.

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

Recommendations

• scientific article; zbMATH DE number 6909264
• Refining the bijections among ascent sequences, (2+2)-free posets, integer matrices and pattern-avoiding permutations
• Refining the bijections among ascent sequences, \((2+2)\)-free posets, integer matrices and pattern-avoiding permutations
• Enumerating \((2 + 2)\)-free posets by indistinguishable elements
• On a conjecture about enumerating \((2+2)\)-free posets
• scientific article; zbMATH DE number 6806834
• Pattern avoidance in poset permutations
• Enumerating \((\mathbf 2+\mathbf 2)\)-free posets by the number of minimal elements and other statistics
• Asymptotic enumeration of permutations avoiding generalized patterns
• Pattern avoidance in alternating permutations and tableaux (extended abstract)

zbMATH Keywords

encodeinvolutionchord diagramascent sequencepattern avoiding permutation(2+2)-free posetenumeratenon-D-finite series

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial identities, bijective combinatorics (05A19) Combinatorics of partially ordered sets (06A07)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Intransitive indifference with unequal indifference intervals
• Generalized permutation patterns and a classification of the Mahonian statistics
• Intransitive Indifference in Preference Theory: A Survey
• Crossings and nestings of matchings and partitions
• Vassiliev invariants and a strange identity related to the Dedekind eta-function
• Generating trees and the Catalan and Schröder numbers
• Resurrecting the asymptotics of linear recurrences
• A direct encoding of Stoimenow's matchings as ascent sequences
• ENUMERATION OF CHORD DIAGRAMS AND AN UPPER BOUND FOR VASSILIEV INVARIANTS
• An obvious proof of Fishburn's interval order theorem
• A characterization of \((3+1)\)-free posets
• Restricted permutations and the wreath product
• Growth diagrams, and increasing and decreasing chains in fillings of Ferrers shapes
• Betweenness, orders and interval graphs
• Height counting of unlabeled interval and \(N\)-free posets.
• Title not available (Why is that?)
• Counting interval orders
• Permutation classes of polynomial growth
• The umbral transfer-matrix method. I: Foundations
• Forest-like permutations

Cited In (83)

• Combinatorial generation via permutation languages. I. Fundamentals
• Stanley-Wilf limits for patterns in rooted labeled forests
• Moments of permutation statistics and central limit theorems
• Enumerating pattern-avoiding Fishburn permutations subject to seven statistics
• Schröder partitions, Schröder tableaux and weak poset patterns
• An operator on ascent sequences
• Algorithmic coincidence classification of mesh patterns
• Fishburn trees
• Proof of a bi-symmetric septuple equidistribution on ascent sequences
• Modified ascent sequences and Bell numbers
• Difference ascent sequences
• A combinatorial study of async/await processes
• Title not available (Why is that?)
• Pattern avoidance in weak ascent sequences
• Last symbol distribution in pattern avoiding Catalan words
• Ascent sequences avoiding a triple of 3-letter patterns and Fibonacci numbers
• Thresholds for patterns in random permutations with a given number of inversions
• Differential transcendence of Bell numbers and relatives: a Galois theoretic approach
• Bi-symmetric multiple equidistributions on ascent sequences
• The history of the Gothenburg--Reykjavík--Strathclyde combinatorics group
• Dynamical aspects of \(\sigma\)-machines
• On enumeration of pattern-avoiding Fishburn permutations
• The combinatorics of Jeff Remmel
• Hereditary semiorders and enumeration of semiorders by dimension
• Some enumerative results related to ascent sequences
• Shape-Wilf-equivalences for vincular patterns
• Enumerating \((\mathbf 2+\mathbf 2)\)-free posets by the number of minimal elements and other statistics
• Enumerating \((2 + 2)\)-free posets by indistinguishable elements
• Enumeration schemes for vincular patterns
• Title not available (Why is that?)
• Pattern avoidance in ascent sequences
• Wilf-classification of mesh patterns of short length
• On \(\underline{12} 0\)-avoiding inversion and ascent sequences
• Web worlds, web-colouring matrices, and web-mixing matrices
• Patterns of relation triples in inversion and ascent sequences
• Vincular patterns in inversion sequences
• Partitions and partial matchings avoiding neighbor patterns
• Weak ascent sequences and related combinatorial structures
• Structure and enumeration of \((3+1)\)-free posets
• Ascent sequences avoiding pairs of patterns
• On \(q\)-series identities related to interval orders
• Generation and enumeration of some classes of interval orders
• Title not available (Why is that?)
• Coxeter-bicatalan combinatorics
• A new decomposition of ascent sequences and Euler-Stirling statistics
• Bijections for inversion sequences, ascent sequences and 3-nonnesting set partitions
• Combinatorial properties of Catalan pairs
• Congruences for Fishburn numbers modulo prime powers
• Inversion sequences avoiding pairs of patterns
• Catalan pairs: a relational-theoretic approach to Catalan numbers
• Large deviations and ratio limit theorems for pattern-avoiding permutations
• Catalan words avoiding pairs of length three patterns
• On the Möbius function and topology of general pattern posets
• Title not available (Why is that?)
• Ascent sequences and 3-nonnesting set partitions
• Decomposing labeled interval orders as pairs of permutations
• Mesh patterns with superfluous mesh
• On a conjecture about enumerating \((2+2)\)-free posets
• Refining the bijections among ascent sequences, \((2+2)\)-free posets, integer matrices and pattern-avoiding permutations
• Refining the bijections among ascent sequences, (2+2)-free posets, integer matrices and pattern-avoiding permutations
• On pattern-avoiding Fishburn permutations
• Refined enumeration of permutations sorted with two stacks and a \(D_8\)-symmetry
• Asymptotics and statistics on Fishburn matrices: Dimension distribution and a conjecture of Stoimenow
• Exact counting of unlabeled rigid interval posets regarding or disregarding height
• Congruences for Taylor expansions of quantum modular forms
• Symmetric generating functions and Euler-Stirling statistics on permutations
• $n!$ matchings, $n!$ posets
• Efficient generation of restricted growth words
• Equidistributed statistics on matchings and permutations
• Catalan pairs and Fishburn triples
• Counting general and self-dual interval orders
• Asymptotics for the number of row-Fishburn matrices
• Interval posets of permutations
• A polyominoes-permutations injection and tree-like convex polyominoes
• Asymptotics of the extremal excedance set statistic
• Equidistributed statistics on Fishburn matrices and permutations
• Permutation classes and polyomino classes with excluded submatrices
• Asymptotics and statistics on Fishburn matrices and their generalizations
• Enumeration of graded (3+1)-avoiding posets
• Pattern-avoiding ascent sequences of length 3
• Transport of patterns by Burge transpose
• Partition and composition matrices
• Title not available (Why is that?)

Uses Software

• OEIS
• ROTA

This page was built for publication: (2+2)-free posets, ascent sequences and pattern avoiding permutations

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