Partitions and Partial Matchings Avoiding Neighbor Patterns
William Y. C. Chen, Neil J. Y. Fan and Alina F. Y. Zhao
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
AMS Classification: 05A15, 05A19 Keywords: set partition, partial matching, neighbor alignment, left nesting, right nesting, self-modified ascent sequence Download: pdf |