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
DOI: https://doi.org/10.1090/S0002-9939-2010-10678-0
Published electronically: October 7, 2010
MathSciNet review: 2736327
Full-text PDF

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 $ \ensuremath{(\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 $ \ensuremath{(\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 $ \ensuremath{(\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?)

  • 1. K. P. Bogart, An obvious proof of Fishburn's interval order theorem, Discrete Mathematics 118, no. 1-3 (1993) 239-242. MR 1230066 (94g:06001)
  • 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.
  • 3. A. de Médicis, X. G. Viennot, Moments des $ q$-polynômes de Laguerre et la bijection de Foata-Zeilberger, Advances in Applied Mathematics 15 (1994) 262-304. MR 1288802 (95i:05007)
  • 4. M. de Sainte-Catherine, Couplage et Pfaffiens en combinatoire, physique et informatique, Thèse du 3me cycle, Université de Bordeaux I, 1983.
  • 5. M. Dukes, R. Parviainen, Ascent sequences and upper triangular matrices containing non-negative integers, Electronic Journal of Combinatorics 17(1) (2010) #R53 (16 pp.). MR 2607339
  • 6. P. C. Fishburn, Interval Graphs and Interval Orders, Wiley, New York, 1985. MR 798530 (87f:06001)
  • 7. P. C. Fishburn, Intransitive indifference in preference theory: a survey, Operational Research 18 (1970) 207-208. MR 0263445 (41:8050)
  • 8. P. C. Fishburn, Intransitive indifference with unequal indifference intervals, Journal of Mathematical Psychology 7 (1970) 144-149. MR 0253942 (40:7155)
  • 9. A. Kasraoui, J. Zeng, Distribution of crossings, nestings and alignments of two edges in matchings and partitions, Electronic Journal of Combinatorics 13, no. 1 (2006) 12 pp. MR 2212506 (2006k:05021)
  • 10. S. Plouffe, N. J. A. Sloane, The Encyclopedia of Integer Sequences, Academic Press Inc., San Diego, 1995. Electronic version available at www.research.att.com/$ \sim$njas/sequences/. MR 1327059 (96a:11001)
  • 11. R. P. Stanley, Enumerative combinatorics, Vol. 1, volume 49 of Cambridge Studies in Advanced Mathematics, Cambridge University Press, Cambridge, 1997. MR 1442260 (98a:05001)
  • 12. R. P. Stanley, Enumerative combinatorics, Vol. 2, volume 62 of Cambridge Studies in Advanced Mathematics, Cambridge University Press, Cambridge, 1999. MR 1676282 (2000k:05026)
  • 13. A. Stoimenow, Enumeration of chord diagrams and an upper bound for Vassiliev invariants, J. Knot Theory Ramifications 7, no. 1 (1998) 93-114. MR 1611987 (99c:57032)
  • 14. S. Sundaram, The Cauchy identity for Sp($ 2n$), Journal of Combinatorial Theory, Series A 53(2) (1990) 209-238 MR 1041446 (91i:05122)
  • 15. R. L. Wine, J. E. Freund, On the enumeration of decision patterns involving $ n$ means, Annals of Mathematical Statistics 28 (1957) 256-259. MR 0084231 (18:832j)
  • 16. D. Zagier, Vassiliev invariants and a strange identity related to the Dedekind eta-function, Topology 40 (2001) 945-960. MR 1860536 (2002g:11055)

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

DOI: https://doi.org/10.1090/S0002-9939-2010-10678-0
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

American Mathematical Society