Bijections for inversion sequences, ascent sequences and 3-nonnesting set partitions

Sherry H.F. Yan

Applied Mathematics and Computation, 2018, vol. 325, issue C, 24-30

Abstract: Set partitions avoiding k-crossing and k-nesting have been extensively studied from the aspects of both combinatorics and mathematical biology. By using the generating tree technique, the obstinate kernel method and Zeilberger’s algorithm, Lin confirmed a conjecture due independently to the author and Martinez–Savage that asserts inversion sequences with no weakly decreasing subsequence of length 3 and enhanced 3-nonnesting partitions have the same cardinality. In this paper, we provide a bijective proof of this conjecture. Our bijection also enables us to provide a new bijective proof of a conjecture posed by Duncan and Steingrímsson, which was proved by the author via an intermediate structure of growth diagrams for 01-fillings of Ferrers shapes.

Keywords: Inversion sequence; Ascent sequence; Pattern avoiding; 3-nonnesting set partition (search for similar items in EconPapers)
Date: 2018
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300317308809
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:325:y:2018:i:c:p:24-30

DOI: 10.1016/j.amc.2017.12.021

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().