Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



$n!$ matchings, $n!$ posets

Authors: Anders Claesson and Svante Linusson
Journal: Proc. Amer. Math. Soc. 139 (2011), 435-449
MSC (2010): Primary 05A05, 05A15
Published electronically: October 7, 2010
MathSciNet review: 2736327
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information


We show that there are $n!$ matchings on $2n$ points without so-called left (neighbor) nestings. We also define a set of naturally labeled $(\mathbf {2}+\mathbf {2})$-free posets and show that there are $n!$ such posets on $n$ elements. Our work was inspired by Bousquet-Mélou, Claesson, Dukes and Kitaev [J. Combin. Theory Ser. A. 117 (2010) 884–909]. They gave bijections between four classes of combinatorial objects: matchings with no neighbor nestings (due to Stoimenow), unlabeled $(\mathbf {2}+\mathbf {2})$-free posets, permutations avoiding a specific pattern, and so-called ascent sequences. We believe that certain statistics on our matchings and posets could generalize the work of Bousquet-Mélou et al., and we make a conjecture to that effect. We also identify natural subsets of matchings and posets that are equinumerous to the class of unlabeled $(\mathbf {2}+\mathbf {2})$-free posets.

We give bijections that show the equivalence of (neighbor) restrictions on nesting arcs with (neighbor) restrictions on crossing arcs. These bijections are thought to be of independent interest. One of the bijections factors through certain upper-triangular integer matrices that have recently been studied by Dukes and Parviainen [Electron. J. Combin. 17 (2010) #R53].

References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 05A05, 05A15

Retrieve articles in all journals with MSC (2010): 05A05, 05A15

Additional Information

Anders Claesson
Affiliation: School of Computer Science, Reykjavik University, Menntavegi 1, 101 Reykjavik, Iceland

Svante Linusson
Affiliation: Department of Mathematics, KTH-Royal Institute of Technology, SE-100 44 Stockholm, Sweden
MR Author ID: 360616

Received by editor(s): March 24, 2010
Published electronically: October 7, 2010
Additional Notes: The first author was supported by grant no. 090038011 from the Icelandic Research Fund.
The second author is a Royal Swedish Academy of Sciences Research Fellow supported by a grant from the Knut and Alice Wallenberg Foundation.
Communicated by: Jim Haglund
Article copyright: © Copyright 2010 Anders Claesson and Svante Linusson