Partitions and partial matchings avoiding neighbor patterns

DOI10.1016/J.EJC.2011.09.039MaRDI QIDQ412240zbMATH OpenOpenAlexFDO

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

Publication date 4 May 2012

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

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

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)

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.

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

Cites work

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

Cited in

(7)

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

Describes a project that uses

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)