Partitions and partial matchings avoiding neighbor patterns

DOI10.1016/J.EJC.2011.09.039zbMATH Open1236.05016arXiv1009.4535OpenAlexW2059169284MaRDI QIDQ412240FDOQ412240

Alina F. Y. Zhao, Neil J. Y. Fan, William Y. C. Chen

Publication date: 4 May 2012

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

Abstract: We obtain the generating functions for partial matchings avoiding neighbor alignments and for partial matchings avoiding neighbor alignments and left nestings. We show that there is a bijection between partial matchings avoiding three neighbor patterns (neighbor alignments, left nestings and right nestings) and set partitions avoiding right nestings via an intermediate structure of integer compositions. Such integer compositions are known to be in one-to-one correspondence with self-modified ascent sequences or $$-avoiding permutations, as shown by Bousquet-M'elou, Claesson, Dukes and Kitaev.

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

Recommendations

• Partial matchings and pattern avoidance
• Pattern avoidance in matchings and partitions
• Matchings and partial patterns
• Matchings avoiding partial patterns and lattice paths
• Matchings avoiding partial patterns

zbMATH Keywords

generating functionsleft nestingspartial mathings avoiding neighborhood alignmentsright nestings

Mathematics Subject Classification ID

Partitions of sets (05A18) Combinatorial identities, bijective combinatorics (05A19) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• On \(abab\)-free and \(abba\)-free set partitions
• Bell numbers, their relatives, and algebraic differential equations
• Crossings and nestings of matchings and partitions
• A direct encoding of Stoimenow's matchings as ascent sequences
• ENUMERATION OF CHORD DIAGRAMS AND AN UPPER BOUND FOR VASSILIEV INVARIANTS
• (2+2)-free posets, ascent sequences and pattern avoiding permutations
• Ascent sequences and upper triangular matrices containing non-negative integers
• On a class of linked diagrams. I: Enumeration
• On trees and noncrossing partitions
• Non-P-recursiveness of numbers of matchings or linear chord diagrams with many crossings
• Reduction of \(m\)-regular noncrossing partitions
• The On-Line Encyclopedia of Integer Sequences
• $n!$ matchings, $n!$ posets
• Matchings avoiding partial patterns and lattice paths
• Matchings avoiding partial patterns

Cited In (6)

• An operator on ascent sequences
• Partial matchings and pattern avoidance
• On pattern-avoiding partitions
• Regular simple queues of protein contact maps
• Equidistributed statistics on matchings and permutations
• Pattern avoiding partitions and Motzkin left factors

Uses Software

• OEIS

This page was built for publication: Partitions and partial matchings avoiding neighbor patterns

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