Crossings and nestings of matchings and partitions
HTML articles powered by AMS MathViewer
- by William Y. C. Chen, Eva Y. P. Deng, Rosena R. X. Du, Richard P. Stanley and Catherine H. Yan PDF
- Trans. Amer. Math. Soc. 359 (2007), 1555-1575 Request permission
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
- Jinho Baik, Percy Deift, and Kurt 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, DOI 10.1090/S0894-0347-99-00307-0
- Jinho Baik and Eric M. Rains, Algebraic aspects of increasing subsequences, Duke Math. J. 109 (2001), no. 1, 1–65. MR 1844203, DOI 10.1215/S0012-7094-01-10911-3
- Jinho Baik and Eric M. Rains, The asymptotics of monotone subsequences of involutions, Duke Math. J. 109 (2001), no. 2, 205–281. MR 1845180, DOI 10.1215/S0012-7094-01-10921-6
- Hélène Barcelo and Arun Ram, Combinatorial representation theory, New perspectives in algebraic combinatorics (Berkeley, CA, 1996–97) Math. Sci. Res. Inst. Publ., vol. 38, Cambridge Univ. Press, Cambridge, 1999, pp. 23–90. MR 1731814
- Allan Berele, A Schensted-type correspondence for the symplectic group, J. Combin. Theory Ser. A 43 (1986), no. 2, 320–328. MR 867655, DOI 10.1016/0097-3165(86)90070-1
- Dragoš M. Cvetković, Michael Doob, and Horst Sachs, Spectra of graphs, 3rd ed., Johann Ambrosius Barth, Heidelberg, 1995. Theory and applications. MR 1324340
- H. Davenport and A. Schinzel, A combinatorial problem connected with differential equations, Amer. J. Math. 87 (1965), 684–694. MR 190010, DOI 10.2307/2373068
- M. de Sainte-Catherine, Couplages et Pfaffiens en combinatoire, physique et informatique, Ph.D. Thesis, University of Bordeaux I, 1983.
- William Feller, An introduction to probability theory and its applications. Vol. I, 3rd ed., John Wiley & Sons, Inc., New York-London-Sydney, 1968. MR 0228020
- I. P. Goulden, A linear operator for symmetric functions and tableaux in a strip with given trace, Discrete Math. 99 (1992), no. 1-3, 69–77. MR 1158782, DOI 10.1016/0012-365X(92)90367-O
- Dominique Gouyou-Beauchamps, Standard Young tableaux of height $4$ and $5$, European J. Combin. 10 (1989), no. 1, 69–82. MR 977181, DOI 10.1016/S0195-6698(89)80034-4
- David J. Grabiner and Peter Magyar, Random walks in Weyl chambers and the decomposition of tensor powers, J. Algebraic Combin. 2 (1993), no. 3, 239–260. MR 1235279, DOI 10.1023/A:1022499531492
- David J. 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), no. 2, 285–306. MR 1883868, DOI 10.1006/jcta.2001.3216
- Curtis Greene, An extension of Schensted’s theorem, Advances in Math. 14 (1974), 254–265. MR 354395, DOI 10.1016/0001-8708(74)90031-0
- Tom Halverson and Arun Ram, Partition algebras, European J. Combin. 26 (2005), no. 6, 869–921. MR 2143201, DOI 10.1016/j.ejc.2004.06.005
- Tom Halverson and Tim Lewandowski, RSK insertion for set partitions and diagram algebras, Electron. J. Combin. 11 (2004/06), no. 2, Research Paper 24, 24. MR 2195430
- Martin Klazar, Bell numbers, their relatives, and algebraic differential equations, J. Combin. Theory Ser. A 102 (2003), no. 1, 63–87. MR 1970977, DOI 10.1016/S0097-3165(03)00014-1
- M. Korn, Personal communication.
- Sri Gopal Mohanty, Lattice path counting and applications, Probability and Mathematical Statistics, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London-Toronto, Ont., 1979. MR 554084
- R. C. Mullin and R. G. Stanton, A map-theoretic approach to Davenport-Schinzel sequences, Pacific J. Math. 40 (1972), 167–172. MR 302601, DOI 10.2140/pjm.1972.40.167
- John Riordan, The distribution of crossings of chords joining pairs of $2n$ points on a circle, Math. Comp. 29 (1975), 215–222. MR 366686, DOI 10.1090/S0025-5718-1975-0366686-9
- C. Schensted, Longest increasing and decreasing subsequences, Canadian J. Math. 13 (1961), 179–191. MR 121305, DOI 10.4153/CJM-1961-015-3
- Richard P. Stanley, Differential posets, J. Amer. Math. Soc. 1 (1988), no. 4, 919–961. MR 941434, DOI 10.1090/S0894-0347-1988-0941434-9
- 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
- R. Stanley, Supplementary Exercises for Chapter 7 of Enumerative Combinatorics, available at http://www-math.mit.edu/~rstan/ec.
- 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
- Lajos Takács, Ballot problems, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 1 (1962), 154–158. MR 145601, DOI 10.1007/BF01844418
- Jacques Touchard, Sur un problème de configurations et sur les fractions continues, Canad. J. Math. 4 (1952), 2–25 (French). MR 46325, DOI 10.4153/cjm-1952-001-8
- E. T. Whittaker and G. N. Watson, A course of modern analysis, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1996. An introduction to the general theory of infinite processes and of analytic functions; with an account of the principal transcendental functions; Reprint of the fourth (1927) edition. MR 1424469, DOI 10.1017/CBO9780511608759
Additional Information
- William Y. C. Chen
- Affiliation: Center for Combinatorics, LPMC, Nankai University, Tianjin 300071, People’s Republic of China
- MR Author ID: 232802
- 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
- MR Author ID: 166285
- 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
- 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. - © Copyright 2006
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Trans. Amer. Math. Soc. 359 (2007), 1555-1575
- MSC (2000): Primary 05A18; Secondary 05E10, 05A15
- DOI: https://doi.org/10.1090/S0002-9947-06-04210-3
- MathSciNet review: 2272140