$n!$ matchings, $n!$ posets
HTML articles powered by AMS MathViewer
- by Anders Claesson and Svante Linusson PDF
- Proc. Amer. Math. Soc. 139 (2011), 435-449
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 10.1016/0012-365X(93)90065-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 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 10.1016/0012-365X(85)90042-1
- Peter C. Fishburn, Intransitive indifference in preference theory: A survey, Operations Res. 18 (1970), 207–228. MR 263445, DOI 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 10.1016/0022-2496(70)90062-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, DOI 10.1017/CBO9780511805967
- 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, DOI 10.1017/CBO9780511609589
- 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 10.1142/S0218216598000073
- Sheila Sundaram, The Cauchy identity for $\textrm {Sp}(2n)$, J. Combin. Theory Ser. A 53 (1990), no. 2, 209–238. MR 1041446, DOI 10.1016/0097-3165(90)90058-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 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 10.1016/S0040-9383(00)00005-7
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
- © Copyright 2010 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
- MathSciNet review: 2736327