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)- 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
- The combinatorics of associated Hermite polynomials
- Fillings of skew shapes avoiding diagonal patterns
- 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)
