Dyck paths and pattern-avoiding matchings

DOI10.1016/J.EJC.2005.07.013zbMATH Open1106.05004OpenAlexW1992104349MaRDI QIDQ854822FDOQ854822

Authors Vít Jelínek

Publication date 7 December 2006

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

configurationcrossing edges

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: How many matchings on the vertex set V={1,2,...,2n} avoid a given configuration of three edges? Chen, Deng and Du have shown that the number of matchings that avoid three nesting edges is equal to the number of matchings avoiding three pairwise crossing edges. In this paper, we consider other forbidden configurations of size three. We present a bijection between matchings avoiding three crossing edges and matchings avoiding an edge nested below two crossing edges. This bijection uses non-crossing pairs of Dyck paths of length 2n as an intermediate step. Apart from that, we give a bijection that maps matchings avoiding two nested edges crossed by a third edge onto the matchings avoiding all configurations from an infinite family, which contains the configuration consisting of three crossing edges. We use this bijection to show that for matchings of size n>3, it is easier to avoid three crossing edges than to avoid two nested edges crossed by a third edge. In this updated version of this paper, we add new references to papers that have obtained analogous results in a different context.

Recommendations

• Pattern-avoiding Dyck paths
• Dyck paths and restricted permutations
• Dyck paths, standard Young tableaux, and pattern avoiding permutations
• A refinement of Dyck paths: A combinatorial approach
• Matchings avoiding partial patterns and lattice paths
• Dyck path enumeration
• On generalized Dyck paths
• Dyck paths with catastrophes modulo the positions of a given pattern
• Permutations and pairs of Dyck paths
• Generalized Dyck paths

Cites work

• scientific article; zbMATH DE number 3987281 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• A bijection between realizers of maximal plane graphs and pairs of non-crossing Dyck paths
• A simple and unusual bijection for Dyck paths and its consequences
• Crossings and nestings of matchings and partitions
• Fixed points and excedances in restricted permutations
• Restricted Motzkin permutations, Motzkin paths, continued fractions, and Chebyshev polyno\-mials
• The On-Line Encyclopedia of Integer Sequences

Cited in

(14)

• Enumeration of some classes of pattern avoiding matchings, with a glimpse into the matching pattern poset
• An infinite family of inv-Wilf-equivalent permutation pairs
• A general theory of Wilf-equivalence for Catalan structures
• Counting with Borel's triangle
• \(k\)-noncrossing and \(k\)-nonnesting graphs and fillings of Ferrers diagrams
• Ordered unavoidable sub-structures in matchings and random matchings
• Pattern avoidance in matchings and partitions
• The combinatorics of associated Hermite polynomials
• Partial Dyck paths with Air Pockets
• The combinatorics of a tree-like functional equation for connected chord diagrams
• Matchings avoiding partial patterns and lattice paths
• On pattern avoidance in matchings and involutions
• Fillings of skew shapes avoiding diagonal patterns
• Patterns in ordered (random) matchings

This page was built for publication: Dyck paths and pattern-avoiding matchings

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