Crossings and nestings of matchings and partitions

Chen, William; Deng, Eva; Du, Rosena; Stanley, Richard; Yan, Catherine

doi:10.1090/S0002-9947-06-04210-3

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