Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Crossings and nestings of matchings and partitions

Authors: William Y. C. Chen, Eva Y. P. Deng, Rosena R. X. Du, Richard P. Stanley and Catherine H. Yan
Journal: Trans. Amer. Math. Soc. 359 (2007), 1555-1575
MSC (2000): Primary 05A18; Secondary 05E10, 05A15
Published electronically: September 19, 2006
MathSciNet review: 2272140
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We present results on the enumeration of crossings and nestings for matchings and set partitions. Using a bijection between partitions and vacillating tableaux, we show that if we fix the sets of minimal block elements and maximal block elements, the crossing number and the nesting number of partitions have a symmetric joint distribution. It follows that the crossing numbers and the nesting numbers are distributed symmetrically over all partitions of $ [n]$, as well as over all matchings on $ [2n]$. As a corollary, the number of $ k$-noncrossing partitions is equal to the number of $ k$-nonnesting partitions. The same is also true for matchings. An application is given to the enumeration of matchings with no $ k$-crossing (or with no $ k$-nesting).

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

  • 1. J. Baik, P. Deift and K. Johansson, On the distribution of the length of the longest increasing subsequence of random permutations. J. Amer. Math. Soc., 12 (1999), No. 4, 1119-1178.MR 1682248 (2000e:05006)
  • 2. J. Baik and E. Rains, Algebraic aspects of increasing subsequences, Duke Math. J., 109 (2001), No. 1, 1-65. MR 1844203 (2002i:05119)
  • 3. J. Baik and E. Rains, The asymptotics of monotone subsequences of involutions, Duke Math. J., 109 (2001), 205-282. MR 1845180 (2003e:60016)
  • 4. H. Barcelo and A. Ram, Combinatorial representation theory, in New Perspectives in Algebraic Combinatorics (Berkeley, CA, 1996-97), MSRI Publ. 38, Cambridge University Press, Cambridge, 1999, pp. 23-90.MR 1731814 (2000j:05125)
  • 5. A. Berele, A Schensted-type correspondence for the symplectic group, J. Combinatorial Theory (A), 43 (1986), 320-328.MR 0867655 (88b:20027)
  • 6. D. M. Cvetkovic, M. Doob, and H. Sachs, Spectra of Graphs. 3rd ed., Johann Ambrosius Barth, Heidelberg, 1995.MR 1324340 (96b:05108)
  • 7. H. Davenport and A. Schinzel, A combinatorial problem connected with differential equations, Amer. J. Math., 87 (1965), 684-694.MR 0190010 (32:7426)
  • 8. M. de Sainte-Catherine, Couplages et Pfaffiens en combinatoire, physique et informatique, Ph.D. Thesis, University of Bordeaux I, 1983.
  • 9. W. Feller, An Introduction to Probability Theory and Its Applications, 3rd edition, John Wiley and Sons, Inc., New York, 1968.MR 0228020 (37:3604)
  • 10. I. P. Goulden, A linear operator for symmetric functions and tableaux in a strip with given trace, Discrete Math., 99 (1992), 69-77. MR 1158782 (93f:05100)
  • 11. D. Gouyou-Beauschamps, Standard Young tableaux of height 4 and 5, Europ. J. Combin., 10 (1989), 69-82. MR 0977181 (90b:05013)
  • 12. D. Grabiner and P. Magyar, Random walks in Weyl chambers and the decomposition of tensor powers, J. Alg. Combinatorics, 2 (1993), 239-260.MR 1235279 (94m:05202)
  • 13. D. Grabiner, Random walk in an alcove of an affine Weyl group, and non-colliding random walks on an interval, J. Combin. Theory Ser. A, 97 (2002), 285-306. MR 1883868 (2002k:60032)
  • 14. C. Greene, An extension of Schensted's theorem, Adv. Math., 14 (1974), 254-265.MR 0354395 (50:6874)
  • 15. T. Halverson and A. Ram, Partition algebras, European J. of Combinatorics, 26 (2005), No. 6, 869-921. MR 2143201 (2006g:05228)
  • 16. T. Halverson and T. Lewandowski, RSK insertion for set partitions and diagram algebras, Electron. J. Combin. 11 (2004/06), no. 2, Research Paper 24, 24 pp. MR 2195430
  • 17. M. Klazar, Bell numbers, their relatives, and algebraic differential equations, J. Combin. Theory Ser. A, 102 (2003), 63-87. MR 1970977 (2004d:11014)
  • 18. M. Korn, Personal communication.
  • 19. S. G. Mohanty, Lattice Path Counting and Applications, Academic Press, New York, 1979.MR 0554084 (81f:60020)
  • 20. R. C. Mullin and R. C. Stanton, A map-theoretic approach to Davenport-Schinzel sequences, Pacific J. Math., 40 (1972), 167-172.MR 0302601 (46:1745)
  • 21. J. Riordan, The distribution of crossings chords joining pairs of $ 2n$ points on a circle, Math. Computation, 29 (1975), 215-222.MR 0366686 (51:2933)
  • 22. C. E. Schensted, Longest increasing and decreasing subsequences, Canad. J. Math., 13 (1961), 179-191. MR 0121305 (22:12047)
  • 23. R. Stanley, Differential posets, J. Amer. Math. Soc., 1 (1988), 919-961.MR 0941434 (89h:06005)
  • 24. R. Stanley, Enumerative Combinatorics, vol. 1, Wadsworth and Brooks/Cole, Pacific Grove, CA, 1986; second printing, Cambridge University Press, Cambridge, 1996. MR 1442260 (98a:05001)
  • 25. R. Stanley, Enumerative Combinatorics, vol. 2, Cambridge University Press, Cambridge, 1999. MR 1676282 (2000k:05026)
  • 26. R. Stanley, Supplementary Exercises for Chapter 7 of Enumerative Combinatorics, available at$ \sim$rstan/ec.
  • 27. S. Sundaram, The Cauchy identity for Sp$ (2n)$, J. Combin. Theory Ser. A, 53 (1990), 209-238. MR 1041446 (91i:05122)
  • 28. L. Takács, Ballot problems, Z. Wahrsch. Verw. Gebiete, 1 (1962), 154-158.MR 0145601 (26:3131)
  • 29. J. Touchard, Sur un problème de configuration et sur les fractions continues, Canad. J. Math., 14 (1952), 2-25.MR 0046325 (13:716c)
  • 30. E. T. Whittaker and G. N. Watson, A Course of Modern Analysis, Cambridge University Press, Cambridge, 1927. MR 1424469 (97k:01072)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 05A18, 05E10, 05A15

Retrieve articles in all journals with MSC (2000): 05A18, 05E10, 05A15

Additional Information

William Y. C. Chen
Affiliation: Center for Combinatorics, LPMC, Nankai University, Tianjin 300071, People’s Republic of China

Eva Y. P. Deng
Affiliation: Center for Combinatorics, LPMC, Nankai University, Tianjin 300071, People’s Republic of China
Address at time of publication: Department of Applied Mathematics, Dalian University of Technology, Dalian, Liaoning 116024, People’s Republic of China

Rosena R. X. Du
Affiliation: Center for Combinatorics, LPMC, Nankai University, Tianjin 300071, People’s Republic of China
Address at time of publication: Department of Mathematics, East China Normal University, Shanghai 200062, People’s Republic of China

Richard P. Stanley
Affiliation: Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

Catherine H. Yan
Affiliation: Department of Mathematics, Texas A&M University, College Station, Texas 77843-3368

Keywords: Crossing, nesting, partition, vacillating tableau
Received by editor(s): January 14, 2005
Published electronically: September 19, 2006
Additional Notes: The first author was supported by the 973 Project on Mathematical Mechanization, the National Science Foundation, the Ministry of Education and the Ministry of Science and Technology of China.
The fourth author was supported in part by NSF grant #DMS-9988459
The fifth author was supported in part by NSF grant #DMS-0245526 and a Sloan Fellowship.
Article copyright: © Copyright 2006 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society