Dyck paths and pattern-avoiding matchings

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

Authors: Vít Jelínek 

Publication date: 7 December 2006

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

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.

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

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

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)

Cites Work

• The On-Line Encyclopedia of Integer Sequences
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• A bijection between realizers of maximal plane graphs and pairs of non-crossing Dyck paths
• Restricted Motzkin permutations, Motzkin paths, continued fractions, and Chebyshev polyno\-mials

Cited In (14)

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

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)