𝑛! matchings, 𝑛! posets

Claesson, Anders; Linusson, Svante

doi:10.1090/S0002-9939-2010-10678-0

$n!$ matchings, $n!$ posets

Authors: Anders Claesson and Svante Linusson
Journal: Proc. Amer. Math. Soc. 139 (2011), 435-449
MSC (2010): Primary 05A05, 05A15
DOI: https://doi.org/10.1090/S0002-9939-2010-10678-0
Published electronically: October 7, 2010
MathSciNet review: 2736327
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract:

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

Kenneth P. Bogart, An obvious proof of Fishburn’s interval order theorem, Discrete Math. 118 (1993), no. 1-3, 239–242. MR 1230066, DOI https://doi.org/10.1016/0012-365X%2893%2990065-2

M. Bousquet-Mélou, A. Claesson, M. Dukes and S. Kitaev, $(2+2)$-free posets, ascent sequences and pattern avoiding permutations, Journal of Combinatorial Theory Series A 117 (2010) 884–909.

Anne de Médicis and Xavier G. Viennot, Moments des $q$-polynômes de Laguerre et la bijection de Foata-Zeilberger, Adv. in Appl. Math. 15 (1994), no. 3, 262–304 (French). MR 1288802, DOI https://doi.org/10.1006/aama.1994.1010

M. de Sainte-Catherine, Couplage et Pfaffiens en combinatoire, physique et informatique, Thèse du 3me cycle, Université de Bordeaux I, 1983.

Mark Dukes and Robert Parviainen, Ascent sequences and upper triangular matrices containing non-negative integers, Electron. J. Combin. 17 (2010), no. 1, Research Paper 53, 16. MR 2607339

Peter C. Fishburn, Interval graphs and interval orders, Discrete Math. 55 (1985), no. 2, 135–149. MR 798530, DOI https://doi.org/10.1016/0012-365X%2885%2990042-1

Peter C. Fishburn, Intransitive indifference in preference theory: A survey, Operations Res. 18 (1970), 207–228. MR 263445, DOI https://doi.org/10.1287/opre.18.2.207

Peter C. Fishburn, Intransitive indifference with unequal indifference intervals, J. Mathematical Psychology 7 (1970), 144–149. MR 253942, DOI https://doi.org/10.1016/0022-2496%2870%2990062-3

Anisse Kasraoui and Jiang Zeng, Distribution of crossings, nestings and alignments of two edges in matchings and partitions, Electron. J. Combin. 13 (2006), no. 1, Research Paper 33, 12. MR 2212506

N. J. A. Sloane and Simon Plouffe, The encyclopedia of integer sequences, Academic Press, Inc., San Diego, CA, 1995. With a separately available computer disk. MR 1327059

Richard P. Stanley, Enumerative combinatorics. Vol. 1, Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, Cambridge, 1997. With a foreword by Gian-Carlo Rota; Corrected reprint of the 1986 original. MR 1442260

Richard P. Stanley, Enumerative combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics, vol. 62, Cambridge University Press, Cambridge, 1999. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin. MR 1676282

A. Stoimenow, Enumeration of chord diagrams and an upper bound for Vassiliev invariants, J. Knot Theory Ramifications 7 (1998), no. 1, 93–114. MR 1611987, DOI https://doi.org/10.1142/S0218216598000073

Sheila Sundaram, The Cauchy identity for ${\rm Sp}(2n)$, J. Combin. Theory Ser. A 53 (1990), no. 2, 209–238. MR 1041446, DOI https://doi.org/10.1016/0097-3165%2890%2990058-5

R. L. Wine and John E. Freund, On the enumeration of decision patterns involving $n$ means, Ann. Math. Statist. 28 (1957), 256–259. MR 84231, DOI https://doi.org/10.1214/aoms/1177707051

Don Zagier, Vassiliev invariants and a strange identity related to the Dedekind eta-function, Topology 40 (2001), no. 5, 945–960. MR 1860536, DOI https://doi.org/10.1016/S0040-9383%2800%2900005-7