×

zbMATH — the first resource for mathematics

Crossings and nestings of matchings and partitions. (English) Zbl 1108.05012
Summary: 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).

MSC:
05A18 Partitions of sets
05E10 Combinatorial aspects of representation theory
05A15 Exact enumeration problems, generating functions
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] 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. · Zbl 0932.05001
[2] Jinho Baik and Eric M. Rains, Algebraic aspects of increasing subsequences, Duke Math. J. 109 (2001), no. 1, 1 – 65. · Zbl 1007.05096 · doi:10.1215/S0012-7094-01-10911-3 · doi.org
[3] Jinho Baik and Eric M. Rains, The asymptotics of monotone subsequences of involutions, Duke Math. J. 109 (2001), no. 2, 205 – 281. · Zbl 1007.60003 · doi:10.1215/S0012-7094-01-10921-6 · doi.org
[4] 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. · Zbl 0939.05083
[5] Allan Berele, A Schensted-type correspondence for the symplectic group, J. Combin. Theory Ser. A 43 (1986), no. 2, 320 – 328. · Zbl 0633.05009 · doi:10.1016/0097-3165(86)90070-1 · doi.org
[6] Dragoš M. Cvetković, Michael Doob, and Horst Sachs, Spectra of graphs, 3rd ed., Johann Ambrosius Barth, Heidelberg, 1995. Theory and applications. · Zbl 0824.05046
[7] H. Davenport and A. Schinzel, A combinatorial problem connected with differential equations, Amer. J. Math. 87 (1965), 684 – 694. · Zbl 0132.00601 · doi:10.2307/2373068 · doi.org
[8] M. de Sainte-Catherine, Couplages et Pfaffiens en combinatoire, physique et informatique, Ph.D. Thesis, University of Bordeaux I, 1983.
[9] William Feller, An introduction to probability theory and its applications. Vol. I, Third edition, John Wiley & Sons, Inc., New York-London-Sydney, 1968. · Zbl 0077.12201
[10] 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. · Zbl 0782.05087 · doi:10.1016/0012-365X(92)90367-O · doi.org
[11] Dominique Gouyou-Beauchamps, Standard Young tableaux of height 4 and 5, European J. Combin. 10 (1989), no. 1, 69 – 82. · Zbl 0672.05012 · doi:10.1016/S0195-6698(89)80034-4 · doi.org
[12] 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. · Zbl 0780.60069 · doi:10.1023/A:1022499531492 · doi.org
[13] 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. · Zbl 1005.05006 · doi:10.1006/jcta.2001.3216 · doi.org
[14] Curtis Greene, An extension of Schensted’s theorem, Advances in Math. 14 (1974), 254 – 265. · Zbl 0303.05006 · doi:10.1016/0001-8708(74)90031-0 · doi.org
[15] Tom Halverson and Arun Ram, Partition algebras, European J. Combin. 26 (2005), no. 6, 869 – 921. · Zbl 1112.20010 · doi:10.1016/j.ejc.2004.06.005 · doi.org
[16] 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. · Zbl 1086.05014
[17] Martin Klazar, Bell numbers, their relatives, and algebraic differential equations, J. Combin. Theory Ser. A 102 (2003), no. 1, 63 – 87. · Zbl 1017.05021 · doi:10.1016/S0097-3165(03)00014-1 · doi.org
[18] M. Korn, Personal communication.
[19] Sri Gopal Mohanty, Lattice path counting and applications, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London-Toronto, Ont., 1979. Probability and Mathematical Statistics. · Zbl 0455.60013
[20] R. C. Mullin and R. G. Stanton, A map-theoretic approach to Davenport-Schinzel sequences, Pacific J. Math. 40 (1972), 167 – 172. · Zbl 0212.34703
[21] John Riordan, The distribution of crossings of chords joining pairs of 2\? points on a circle, Math. Comp. 29 (1975), 215 – 222. Collection of articles dedicated to Derrick Henry Lehmer on the occasion of his seventieth birthday. · Zbl 0319.05004
[22] C. Schensted, Longest increasing and decreasing subsequences, Canad. J. Math. 13 (1961), 179 – 191. · Zbl 0097.25202 · doi:10.4153/CJM-1961-015-3 · doi.org
[23] Richard P. Stanley, Differential posets, J. Amer. Math. Soc. 1 (1988), no. 4, 919 – 961. · Zbl 0658.05006
[24] 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. · Zbl 0889.05001
[25] 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. · Zbl 0928.05001
[26] R. Stanley, Supplementary Exercises for Chapter 7 of Enumerative Combinatorics, available at http://www-math.mit.edu/\( \sim\)rstan/ec.
[27] Sheila Sundaram, The Cauchy identity for \?\?(2\?), J. Combin. Theory Ser. A 53 (1990), no. 2, 209 – 238. · Zbl 0707.05005 · doi:10.1016/0097-3165(90)90058-5 · doi.org
[28] Lajos Takács, Ballot problems, Z. Wahrscheinlichkeitstheorie Verw. Gebiete 1 (1962), 154 – 158. · Zbl 0114.33804 · doi:10.1007/BF01844418 · doi.org
[29] Jacques Touchard, Sur un problème de configurations et sur les fractions continues, Canadian J. Math. 4 (1952), 2 – 25 (French). · Zbl 0047.01801
[30] 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. · JFM 53.0180.04
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.