Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
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 Free Access

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?)


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
Email: chen@nankai.edu.cn

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
Email: dengyp@eyou.com

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
Email: rxdu@math.ecnu.edu.cn

Richard P. Stanley
Affiliation: Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Email: rstan@math.mit.edu

Catherine H. Yan
Affiliation: Department of Mathematics, Texas A&M University, College Station, Texas 77843-3368
Email: cyan@math.tamu.edu

DOI: http://dx.doi.org/10.1090/S0002-9947-06-04210-3
PII: S 0002-9947(06)04210-3
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.